Abstract
Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph G on n vertices with maximum degree 4 (4-planar graph) and for each edge e a cost function coste : N0 → R defining costs depending on the number of bends e has, compute a planar orthogonal drawing of G of minimum cost.
In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time O(n, ⋅, Tflow(n) and O(n2, ⋅, Tflow(n)) for biconnected and connected graphs, respectively, where Tflow(n) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
- Therese Biedl and Goos Kant. 1998. A better heuristic for orthogonal graph drawings. Comput. Geom. 9, 3 (1998), 159--180. Google ScholarDigital Library
- Thomas Bläsius, Marcus Krug, Ignaz Rutter, and Dorothea Wagner. 2014. Orthogonal graph drawing with flexibility constraints. Algorithmica 68, 4 (2014), 859--885.Google ScholarCross Ref
- Thomas Bläsius, Sebastian Lehmann, and Ignaz Rutter. 2015. Orthogonal graph drawing with inflexible edges. In Algorithms and Complexity (CIAC’15) (LNCS), Vangelis Th. Paschos and Peter Widmayer (Eds.), Vol. 9079. Springer, Berlin, 61--73.Google Scholar
- G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen. 2011. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In Proc. Foundations of Computer Science (FOCS’11). IEEE, Washington, DC, 170--179. Google ScholarDigital Library
- Sabine Cornelsen and Andreas Karrenbauer. 2012. Accelerated bend minimization. In Graph Drawing (GD’11) (LNCS), Vol. 7034. Springer, Berlin, 111--122. Google ScholarDigital Library
- G. Di Battista, G. Liotta, and F. Vargiu. 1998. Spirality and optimal orthogonal drawings. SIAM J. Comput. 27, 6 (1998), 1764--1811. Google ScholarDigital Library
- G. Di Battista and R. Tamassia. 1996a. On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15, 4 (1996), 302--318.Google ScholarDigital Library
- G. Di Battista and R. Tamassia. 1996b. On-line planarity testing. SIAM J. Comput. 25, 5 (1996), 956--997. Google ScholarDigital Library
- Jack Edmonds and Richard M. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (1972), 248--264. Google ScholarDigital Library
- Ulrich Fößmeier and Michael Kaufmann. 1995. Drawing high degree graphs with low bend numbers. In Graph Drawing (GD’95) (LNCS). Springer, Berlin, 254--266. Google ScholarDigital Library
- Ashim Garg and Roberto Tamassia. 2001. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31, 2 (2001), 601--625. Google ScholarDigital Library
- Carsten Gutwenger and Petra Mutzel. 2001. A linear time implementation of SPQR-trees. In Graph Drawing (GD’00) (LNCS), Vol. 1984. Springer, Berlin, 77--90. Google ScholarDigital Library
- Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 1 (1997), 3--23. Google ScholarDigital Library
- Gunnar W. Klau and Petra Mutzel. 1998. Quasi-Orthogonal Drawing of Planar Graphs. Technical Report. Max-Planck-Institut für Informatik, Saarbrücken, Germany.Google Scholar
- Aurora Morgana, Célia Picinin de Mello, and Giovanna Sontacchi. 2004. An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid. Discr. Appl. Math. 141, 1--3 (2004), 225--241. Google ScholarDigital Library
- James B. Orlin. 1993. A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41 (1993), 338--350. Issue 2.Google ScholarDigital Library
- Ignaz Rutter. 2011. The Many Faces of Planarity—Matching, Augmentation, and Embedding Algorithms for Planar Graphs. Ph.D. Dissertation. Fakultät für Informatik, Karlsruher Institut für Technologie (KIT).Google Scholar
- Roberto Tamassia. 1987. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16, 3 (1987), 421--444. Google ScholarDigital Library
- R. Tamassia, G. Di Battista, and C. Batini. 1988. Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man Cybern. 18, 1 (1988), 61--79. Google ScholarDigital Library
- Satoshi Tayu, Kumiko Nomura, and Shuichi Ueno. 2009. On the two-dimensional orthogonal drawing of series-parallel graphs. Discr. Appl. Math. 157, 8 (2009), 1885--1895. Google ScholarDigital Library
- Hassler Whitney. 1932. Non-separable and planar graphs. Trans. Am. Math. Soc. 34, 2 (April 1932), 339--338.Google ScholarCross Ref
Index Terms
- Optimal Orthogonal Graph Drawing with Convex Bend Costs
Recommendations
Optimal orthogonal graph drawing with convex bend costs
ICALP'13: Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part ITraditionally, the quality of orthogonal planar drawings is quantified by the total number of bends, or the maximum number of bends per edge. However, this neglects that in typical applications, edges have varying importance. We consider the problem ...
The DFS-heuristic for orthogonal graph drawing
In this paper, we present a new heuristic for orthogonal graph drawings, which creates drawings by performing a depth-first search and placing the nodes in the order they are encountered. This DFS-heuristic works for graphs with arbitrarily high degrees,...
Bend-optimal orthogonal graph drawing in the general position model
We consider orthogonal drawings in the general position model, i.e., no two points share a coordinate. The drawings are also required to be bend minimal, i.e., each edge of a drawing in k dimensions has exactly one segment parallel to each coordinate ...
Comments