×

zbMATH — the first resource for mathematics

How to draw a planarization. (English) Zbl 1419.05200
Summary: We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossing-minimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd [P. Simonetto et al., “ImPrEd: An improved force-directed algorithm that prevents nodes from crossing edges”, Comput. Graph. Forum 30, No. 3, 1071–1080 (2011; doi:10.1111/j.1467-8659.2011.01956.x)], the second approach, which we call geometric planarization drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing. Our evaluation shows that both approaches significantly improve the initial drawing and that our geometric approach outperforms the force-directed approach. To the best of our knowledge, this is the first paper concerned with the generation of a straight-line drawing that respects an arbitrary planarization.
MSC:
05C85 Graph algorithms (graph-theoretic aspects)
Software:
Moca; OGDF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Bertault.A Force-Directed Algorithm that Preserves Edge-Crossing Properties. Information Processing Letters, 74(1-2):7-13, 2000. · Zbl 1014.68201
[2] T. Bl¨asius, M. Radermacher, and I. Rutter. How to Draw a Planarization. In B. Steffen, C. Baier, M. van den Brand, J. Eder, M. Hinchey, and T. Margaria, editors, Proceedings of the 43rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM’17), pages 295-308. Springer International Publishing, 2017. · Zbl 1445.68150
[3] B. M. ´Abrego, S. Fern´andez-Merchant, J. Lea˜nos, and G. Salazar. The Maximum Number of Halving Lines and the Rectilinear Crossing Number of Knfor n ≤ 27. Electronic Notes in Discrete Mathematics, 30:261 - 266, 2008. · Zbl 1341.05034
[4] C. Buchheim, M. Chimani, C. Gutwenger, M. J¨unger, and P. Mutzel. Crossings and Planarization. In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, pages 43-85. Chapman and Hall/CRC, 2013.
[5] E. W. Chambers, D. Eppstein, M. T. Goodrich, and M. L¨offler. Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area. Journal of Graph Algorithms and Applications, 16(2):243-259, 2012. · Zbl 1254.05122
[6] T. M. Chan, F. Frati, C. Gutwenger, A. Lubiw, P. Mutzel, and M. Schaefer. Drawing Partially Embedded and Simultaneously Planar Graphs. Journal of Graph Algorithms and Applications, 19(2):681-706, 2015. · Zbl 1328.05130
[7] M. Chimani, C. Gutwenger, M. J¨unger, G. W. Klau, K. Klein, and P. Mutzel.The open graph drawing framework (ogdf).In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, pages 543-569. Chapman and Hall/CRC, 2013.
[8] G. Da Lozzo, V. Dujmovic, F. Frati, T. Mchedlidze, and V. Roselli. Drawing Planar Graphs with Many Collinear Vertices. Journal of Computational Geometry, 9(1):94-130, 2018. · Zbl 1417.68156
[9] W. Didimo, G. Liotta, and F. Montecchiani. A Survey on Graph Drawing Beyond Planarity. ACM Computating Surveys, 52(1):4:1-4:37, 2019.
[10] W. Didimo, G. Liotta, and S. A. Romeo. Topology-Driven Force-Directed Algorithms. In U. Brandes and S. Cornelsen, editors, Proceedings of the 18th International Symposium on Graph Drawing (GD’10), volume 6502 of Lecture Notes in Computer Science, pages 165-176. Springer, 2011. · Zbl 1314.68225
[11] T. Dwyer, K. Marriott, and M. Wybrow. Topology Preserving Constrained Graph Layout.In I. G. Tollis and M. Patrignani, editors, Proceedings of the 16th International Symposium on Graph Drawing (GD’08), volume 5417 of Lecture Notes in Computer Science, pages 230-241. Springer Berlin/Heidelberg, 2009. · Zbl 1213.68441
[12] P. Eades, S.-H. Hong, G. Liotta, N. Katoh, and S.-H. Poon. Straight-Line Drawability of a Planar Graph Plus an Edge. In F. Dehne, J.-R. Sack, and U. Stege, editors, Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS’15), volume 9214 of Lecture Notes in Computer Science, pages 301-313. Springer International Publishing, 2015. · Zbl 1444.68141
[13] E. D. Giacomo, P. Eades, G. Liotta, H. Meijer, and F. Montecchiani. Polyline Drawings with Topological Constraints.In W.-L. Hsu, D.-T. Lee, and C.-S. Liao, editors, Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC’18), volume 123 of Leibniz International Proceedings in Informatics, pages 39:1-39:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[14] L. Grilli, S.-H. Hong, J. Kratochv´ıl, and I. Rutter. Drawing Simultaneously Embedded Graphs with Few Bends. In C. Duncan and A. Symvonis, editors, Proceedings of the 22nd International Symposium on Graph Drawing (GD’14), volume 8871 of Lecture Notes in Computer Science, pages 40-51. Springer Berlin/Heidelberg, 2014. · Zbl 1426.68212
[15] C. Gutwenger, P. Mutzel, and R. Weiskircher.Inserting an Edge Into a Planar Graph.Algorithmica, 41(4):289-308, 2005. · Zbl 1065.68075
[16] S. Huber and M. Held. Motorcycle graphs: Stochastic Properties Motivate an Efficient yet Simple Implementation. Journal of Experimental Algorithmics, 16:1-3, 2011. · Zbl 1284.68297
[17] S. Huber and M. Held.A Fast Straight-Skeleton Algorithm Based on Generalized Motorcycle Graphs.International Journal of Computational Geometry & Applications, 22(05):471-498, 2012. · Zbl 1267.68167
[18] B. Joe and R. B. Simpson. Corrections to Lee’s Visibility Polygon Algorithm. BIT Numerical Mathematics, 27(4):458-473, 1987. · Zbl 0643.68098
[19] G. Kant. Drawing Planar Graphs Using the Canonical Ordering. Algorithmica, 16(1):4-32, 1996. · Zbl 0851.68086
[20] T. Mchedlidze, M. N¨ollenburg, and I. Rutter.Extending Convex Partial Drawings of Graphs. Algorithmica, 76(1):47-67, 2016. · Zbl 1348.68176
[21] T. Mchedlidze, M. Radermacher, and I. Rutter. Aligned Drawings of Planar Graphs. Journal of Graph Algorithms and Applications, 22(3):401-429, 2018. · Zbl 1398.05143
[22] N. E. Mn¨ev. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties. In O. Y. Viro and A. M. Vershik, editors, Topology and Geometry — Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pages 527-543. Springer Berlin/Heidelberg, 1988.
[23] J. Nievergelt and F. P. Preparata. Plane-Sweep Algorithms for Intersecting Geometric Figures. Communications of the ACM, 25(10):739-747, 1982. · Zbl 0491.68075
[24] M. Radermacher, K. Reichard, I. Rutter, and D. Wagner.Geometric Heuristics for Rectilinear Crossing Minimization. Journal of Experimental Algorithmics, 24(1):1.12:1-1.12:21, 2019. · Zbl 1430.68236
[25] M. Radermacher and I. Rutter. Inserting an Edge into a Geometric Embedding. In T. C. Biedl and A. Kerren, editors, Proceedings of the 26th International Symposium on Graph Drawing (GD’18), volume 11282 of Lecture Notes in Computer Science, pages 402-415. Springer International Publishing, 2018. · Zbl 07023840
[26] M. Schaefer. Complexity of Some Geometric and Topological Problems. In D. Eppstein and E. R. Gansner, editors, Proceedings of the 17th International Symposium on Graph Drawing (GD’09), volume 5849 of Lecture Notes in Computer Science, pages 334-344. Springer Berlin/Heidelberg, 2010. · Zbl 1284.68305
[27] D. J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures. Chapman and Hall/CRC, 2003. · Zbl 0861.62001
[28] P. Simonetto, D. Archambault, D. Auber, and R. Bourqui. ImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges. Computer Graphics Forum, 30(3):1071-1080, 2011.
[29] R. Tamassia.On Embedding a Graph in the Grid with the Minimum Number of Bends.SIAM Journal on Computing, 16(3):421-444, 1987. · Zbl 0654.68090
[30] C. Thomassen. Rectilinear Drawings of Graphs. Journal of Graph Theory, 12(3):335-341, 1988. · Zbl 0649.05051
[31] W. T. Tutte. How to Draw a Graph. Proceedings of the London Mathematical Society, s3-13(1):743-767, 1963. · Zbl 0115.40805
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.