Inserting an edge into a geometric embedding. (English) Zbl 1483.68261
Authors’ abstract: The algorithm to insert an edge \(e\) in linear time into a planar graph \(G\) with a minimal number of crossings on \(e\) [C. Gutwenger et al., Algorithmica 41, No. 4, 289–308 (2005; Zbl 1065.68075)] is a helpful tool for designing heuristics that minimize edge crossings in topological drawings of general graphs. Unfortunately, not all such topological drawings are stretchable, i.e., there may not exist an equivalent straight-line drawing. That is, there is no planar straight-line drawing \(\Gamma\) of \(G\) such that in \(\Gamma + e\) the edge \(e\) crosses the same edges as in the topological drawing of \(G + e\) and it does so in the same order. This motivates the study of the computational complexity of the problem Geometric Edge Insertion: Given a combinatorially embedded graph \(G\), compute a geometric embedding \(\Gamma\) of \(G\) that minimizes the crossings in \(\Gamma + e\).
We give a characterization of the stretchable topological drawings of \(G + e\) that also applies to the case where the outer face is fixed; this answers an open question of P. Eades et al. [Lect. Notes Comput. Sci. 9214, 301–313 (2015; Zbl 1444.68141)]. Algorithmically, we focus on the case where the outer face is not fixed. We show that Geometric Edge Insertion can be solved efficiently for graphs of maximum degree 5. For the general case, we show a \((\Delta - 2)\)-approximation, where \(\Delta\) is the maximum vertex degree of \(G\) and an FPT algorithm with respect to the minimum number of crossings. Finally, we consider the problem of testing whether there exists a solution of Geometric Edge Insertion that achieves the lower bound obtained by a topological insertion.
We give a characterization of the stretchable topological drawings of \(G + e\) that also applies to the case where the outer face is fixed; this answers an open question of P. Eades et al. [Lect. Notes Comput. Sci. 9214, 301–313 (2015; Zbl 1444.68141)]. Algorithmically, we focus on the case where the outer face is not fixed. We show that Geometric Edge Insertion can be solved efficiently for graphs of maximum degree 5. For the general case, we show a \((\Delta - 2)\)-approximation, where \(\Delta\) is the maximum vertex degree of \(G\) and an FPT algorithm with respect to the minimum number of crossings. Finally, we consider the problem of testing whether there exists a solution of Geometric Edge Insertion that achieves the lower bound obtained by a topological insertion.
Reviewer: Xueliang Li (Tianjin)
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Björklund, A.; Husfeldt, T., Shortest two disjoint paths in polynomial time, SIAM J. Comput., 48, 6, 1698-1710 (2019) · Zbl 1428.05292 |
| [2] | Cabello, S.; Mohar, B., Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput., 42, 5, 1803-1829 (2013) · Zbl 1282.05033 |
| [3] | Chimani, M.; Gutwenger, C.; Mutzel, P.; Wolf, C., Inserting a vertex into a planar graph, (Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09) (2009)), 375-383 · Zbl 1421.68111 |
| [4] | Chimani, M.; Hlinený, P., Inserting multiple edges into a planar graph, (Fekete, S.; Lubiw, A., Proceedings of the 32nd Annual Symposium on Computational Geometry (SoCG’16). Proceedings of the 32nd Annual Symposium on Computational Geometry (SoCG’16), Leibniz International Proceedings in Informatics (LIPIcs), vol. 51 (2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik), 30:1-30:15 · Zbl 1388.68216 |
| [5] | Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer International Publishing · Zbl 1334.90001 |
| [6] | Da Lozzo, G.; Dujmovic, V.; Frati, F.; Mchedlidze, T.; Roselli, V., Drawing planar graphs with many collinear vertices, J. Comput. Geom., 9, 1, 94-130 (2018) · Zbl 1417.68156 |
| [7] | Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Flow and upward planarity, (Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice Hall: Prentice Hall New Jersey), 171-214 · Zbl 1057.68653 |
| [8] | Eades, P.; Hong, S. H.; Liotta, G.; Katoh, N.; Poon, S. H., Straight-line drawability of a planar graph plus an edge, (Dehne, F.; Sack, J. R.; Stege, U., Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS’15). Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS’15), Lecture Notes in Computer Science, vol. 9214 (2015), Springer International Publishing), 301-313 · Zbl 1444.68141 |
| [9] | Eilam-Tzoreff, T., The disjoint shortest paths problem, Discrete Appl. Math., 85, 2, 113-138 (1998) · Zbl 0902.68147 |
| [10] | Even, S.; Itai, A.; Shamir, A., On the complexity of time table and multi-commodity flow problems, (16th Annual Symposium on Foundations of Computer Science (SFCS 1975) (1975)), 184-193 |
| [11] | Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theory Comput. Syst., 10, 2, 111-121 (1980) · Zbl 0419.05028 |
| [12] | Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 4, 3, 312-316 (1983) · Zbl 0536.05016 |
| [13] | Gutwenger, C.; Klein, K.; Mutzel, P., Planarity testing and optimal edge insertion with embedding constraints, J. Graph Algorithms Appl., 12, 1, 73-95 (2008) · Zbl 1161.68670 |
| [14] | Gutwenger, C.; Mutzel, P.; Weiskircher, R., Inserting an edge into a planar graph, Algorithmica, 41, 4, 289-308 (2005) · Zbl 1065.68075 |
| [15] | Kobayashi, Y.; Sommer, C., On shortest disjoint paths in planar graphs, Discrete Optim., 7, 4, 234-245 (2010) · Zbl 1241.90163 |
| [16] | Kobourov, S. G., Force-directed drawing algorithms, (Tamassia, R., Handbook of Graph Drawing and Visualization (2013), Chapman and Hall/CRC), Chap. 12 |
| [17] | Mchedlidze, T.; Radermacher, M.; Rutter, I., Aligned drawings of planar graphs, J. Graph Algorithms Appl., 22, 3, 401-429 (2018) · Zbl 1398.05143 |
| [18] | Mnëv, N. E., The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, (Viro, O. Y.; Vershik, A. M., Topology and Geometry — Rohlin Seminar. Topology and Geometry — Rohlin Seminar, Lecture Notes in Mathematics, vol. 1346 (1988), Springer: Springer Berlin/Heidelberg), 527-543 · Zbl 0667.52006 |
| [19] | Radermacher, M.; Reichard, K.; Rutter, I.; Wagner, D., Geometric heuristics for rectilinear crossing minimization, J. Exp. Algorithmics, 24, 1, 1.12:1-1.12:21 (2019) |
| [20] | Radermacher, M.; Rutter, I., Geometric crossing minimization - a scalable randomized approach, (Bender, M. A.; Svensson, O.; Herman, G., Proceedings of the 27th Annual European Symposium on Algorithms (ESA’19). Proceedings of the 27th Annual European Symposium on Algorithms (ESA’19), Leibniz International Proceedings in Informatics (LIPIcs) (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 76:1-76:16 · Zbl 07525513 |
| [21] | Shor, P. W., Stretchability of pseudolines is NP-hard, (Sturmfels, B.; Gritzmann, P., Applied Geometry and Discrete Mathematics-the Victor Klee Festschrift. Applied Geometry and Discrete Mathematics-the Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4 (1991), AMS, DIMACS and ACM), 531-554 · Zbl 0751.05023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
