Abstract
This paper investigates the Orthogonal Compaction (OC) problem, which involves minimizing the area of a grid-based graph drawing while maintaining a fixed orthogonal shape. Given that the general problem is NP-hard, we apply the lens of parameterized complexity to identify tractable instances. We demonstrate that the problem is Fixed-Parameter Tractable (FPT) when parameterized by the number of "kitty corners"—pairs of reflex corners that constrain each other's placement. Additionally, we provide a polynomial kernel for simple cycles and an XP algorithm for drawings of bounded height, while proving that small face degrees do not alleviate the problem's inherent computational difficulty.
Introduction
In graph drawing, an orthogonal drawing represents edges as sequences of horizontal and vertical segments, a format essential for UML diagrams, VLSI layouts, and metro maps. Often, designers start with an "orthogonal representation"—a blueprint specifying the angles at vertices and the sequence of bends on edges—without having exact coordinates.
The goal of Orthogonal Compaction (OC) is to assign integer coordinates to vertices and bends to minimize the total area of the drawing's bounding box. While specific subclasses, such as turn-regular graphs, can be solved efficiently, the general problem is NP-hard. As shown in the figure below, the same orthogonal representation can be realized with significantly different areas depending on the coordinate assignment.
Methods and Parameterized Complexity
To address the NP-hardness of OC, the authors explore several parameters beyond the total number of vertices ($n$):
1. The "Kitty Corner" Parameter
Kitty corners are pairs of reflex corners (270° turns) in a face that "point" at each other. These are identified as the primary source of NP-hardness because they create global dependencies in coordinate assignment. The authors developed an FPT algorithm that runs in $O(2^{8.4k} n \log n)$ time, where $k$ is the number of kitty corners. By "guessing" the relative horizontal and vertical positions of these specific corners, the problem can be decomposed into two independent 1D compaction problems that are solvable in polynomial time.
2. Kernelization and Height Constraints
For the special case of simple cycles, the paper provides a polynomial kernel. This allows a large cycle to be "shrunk" into a smaller equivalent instance whose size depends only on $k$. Furthermore, the authors propose an XP algorithm for graphs with a fixed height $h$, using a dynamic programming approach to process the grid column by column in $n^{O(h)}$ time.
Key Results and Insights
- Theorem 1 (FPT): OC is FPT with respect to the number of kitty corners $k$. This provides an exact algorithm that is efficient for "near-regular" drawings common in practice.
- Theorem 2 (Kernelization): Cycle graphs admit a polynomial kernel through reduction rules that prune "flat" paths of vertices.
- Theorem 3 (Hardness): OC is para-NP-hard when parameterized by maximum face degree. This proves that even if every face is a small polygon, the global area minimization constraints keep the problem difficult.
- Theorem 4 (XP): OC is in XP when parameterized by the height $h$ of the representation.
Conclusion and Future Work
The paper establishes that kitty corners are the fundamental bottleneck in orthogonal compaction. While the FPT result for $k$ is a major theoretical advancement, the current XP algorithm for height leaves open the question of whether an FPT algorithm for height exists. Future research may also focus on optimizing the exponential constant ($2^{8.4k}$) to make the kitty corner algorithm more practical for larger values of $k$.
Summary updated