Document Open Access Logo

Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing

Author Boris Klemz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.57.pdf
  • Filesize: 1.35 MB
  • 15 pages

Document Identifiers

Author Details

Boris Klemz
  • Universität Würzburg, Germany

Funding

  • Klemz, Boris: supported by DFG project WO758/11-1.

Cite AsGet BibTex

Boris Klemz. Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.57

Abstract

A hierarchical plane st-graph H can be thought of as a combinatorial description of a planar drawing Γ of a 2-connected graph G in which each edge is a y-monotone curve and each face encloses a y-monotone region (that is, a region whose intersection with any horizontal line is a line segment, a point, or empty). A drawing Γ' of H is a drawing of G such that each horizontal line intersects the same left-to-right order of edges and vertices in Γ and Γ', that is, the underlying hierarchical plane st-graph of both drawings is H. A straight-line planar drawing of a graph is convex if the boundary of each face is realized as a convex polygon. We study the computation of convex drawings of hierarchical plane st-graphs such that the outer face is realized as a prescribed polygon. Chrobak, Goodrich, and Tamassia [SoCG'96] and, independently, Kleist et al. [CGTA'19] described an idea to solve this problem in O(n^{1.1865}) time, where n is the number of vertices of the graph. Also independently, Hong and Nagamochi [J. Discrete Algorithms'10] described a completely different approach, which can be executed in O(n²) time. In this paper, we present an optimal O(n) time algorithm to solve the above problem, thereby improving the previous results by Chrobak, Goodrich, and Tamassia, Kleist et al., and by Hong and Nagamochi. Our result has applications in graph morphing. A planar morph is a continuous deformation of a graph drawing that preserves straight-line planarity. We show that our algorithm can be used as a drop-in replacement to speed up a procedure by Alamdari et al. [SICOMP'17] to morph between any two given straight-line planar drawings of the same plane graph. The running time improves from O(n^{2.1865}) to O(n²log n). To obtain our results, we devise a new strategy for computing so-called archfree paths in hierarchical plane st-graphs, which might be of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graphs and surfaces
  • Theory of computation → Computational geometry
  • Human-centered computing → Graph drawings
Keywords
  • convex drawing
  • hierarchical graph
  • graph drawing
  • computational geometry
  • planarity
  • planar graph
  • morphing
  • convexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Ferran Hurtado, Anna Lubiw, Günter Rote, André Schulz, Diane L. Souvaine, and Andrew Winslow. Convexifying polygons without losing visibilities. In Greg Aloupis and Bremner, editors, Canadian Conference on Computational Geometry (CCCG), pages 229-234, 2011. Google Scholar
  2. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, and Bryan T. Wilkinson. How to morph planar graph drawings. SIAM J. Comput., 46(2):824-852, 2017. URL: https://doi.org/10.1137/16M1069171.
  3. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  4. Noga Alon and Raphael Yuster. Matrix sparsification and nested dissection over arbitrary fields. Journal of the ACM, 60(4):25, 2013. Google Scholar
  5. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Vincenzo Roselli. The importance of being proper: (in clustered-level planarity and t-level planarity). Theor. Comput. Sci., 571:1-9, 2015. URL: https://doi.org/10.1016/j.tcs.2014.12.019.
  6. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. Morphing planar graph drawings optimally. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 126-137. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_11.
  7. Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, and Vincenzo Roselli. Optimal morphs of convex drawings. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 126-140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.126.
  8. Guido Brückner and Ignaz Rutter. Partial and constrained level planarity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2000-2011. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.130.
  9. Erin Wolf Chambers, Jeff Erickson, Patrick Lin, and Salman Parsa. How to morph graphs on the torus. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2759-2778. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.164.
  10. Marek Chrobak, Michael T. Goodrich, and Roberto Tamassia. Convex drawings of graphs in two and three dimensions (preliminary version). In Sue Whitesides, editor, Proceedings of the Twelfth Annual Symposium on Computational Geometry, Philadelphia, PA, USA, May 24-26, 1996, pages 319-328. ACM, 1996. URL: https://doi.org/10.1145/237218.237401.
  11. Robert Connelly, Erik D. Demaine, and Günter Rote. Straightening polygonal arcs and convexifying polygonal cycles. Discrete & Computational Geometry, 30:205-239, 2003. Google Scholar
  12. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. URL: https://www.worldcat.org/oclc/227584184.
  13. Giuseppe Di Battista and Enrico Nardelli. Hierarchies and planarity theory. IEEE Trans. Systems, Man, and Cybernetics, 18(6):1035-1046, 1988. URL: https://doi.org/10.1109/21.23105.
  14. Peter Eades, Qing-Wen Feng, Xuemin Lin, and Hiroshi Nagamochi. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica, 44(1):1-32, 2006. URL: https://doi.org/10.1007/s00453-004-1144-8.
  15. Michael S. Floater. Parameterization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 14(3):231-250, 1997. Google Scholar
  16. Michael S. Floater. Parametric tilings and scattered data approximation. International Journal of Shape Modeling, 4(03n04):165-182, 1998. Google Scholar
  17. Jonas Gomes, Lucia Darsa, Bruno Costa, and Luiz Velho. Warping and Morphing of Graphical Objects. Morgan Kaufmann, 1999. Google Scholar
  18. Lenwood S. Heath and Sriram V. Pemmaraju. Recognizing leveled-planar dags in linear time. In Franz-Josef Brandenburg, editor, Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings, volume 1027 of Lecture Notes in Computer Science, pages 300-311. Springer, 1995. URL: https://doi.org/10.1007/BFb0021813.
  19. Seok-Hee Hong and Hiroshi Nagamochi. Convex drawings of graphs with non-convex boundary constraints. Discret. Appl. Math., 156(12):2368-2380, 2008. URL: https://doi.org/10.1016/j.dam.2007.10.012.
  20. Seok-Hee Hong and Hiroshi Nagamochi. Convex drawings of hierarchical planar graphs and clustered planar graphs. J. Discrete Algorithms, 8(3):282-295, 2010. URL: https://doi.org/10.1016/j.jda.2009.05.003.
  21. Michael Jünger, Sebastian Leipert, and Petra Mutzel. Level planarity testing in linear time. In Sue Whitesides, editor, Graph Drawing, 6th International Symposium, GD'98, Montréal, Canada, August 1998, Proceedings, volume 1547 of Lecture Notes in Computer Science, pages 224-237. Springer, 1998. URL: https://doi.org/10.1007/3-540-37623-2_17.
  22. Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, and Darren Strash. Convexity-increasing morphs of planar graphs. Comput. Geom., 84:69-88, 2019. URL: https://doi.org/10.1016/j.comgeo.2019.07.007.
  23. Boris Klemz and Günter Rote. Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity. ACM Trans. Algorithms, 15(4):53:1-53:25, 2019. URL: https://doi.org/10.1145/3359587.
  24. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296-303. ACM, 2014. Google Scholar
  25. Richard J. Lipton, Donald J. Rose, and Robert Endre Tarjan. Generalized nested dissection. SIAM J. Numerical Analysis, 16(2):346-358, 1979. Google Scholar
  26. Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: https://doi.org/10.1137/0209046.
  27. Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. Upward planar morphs. Algorithmica, 82(10):2985-3017, 2020. URL: https://doi.org/10.1007/s00453-020-00714-6.
  28. János Pach and Géza Tóth. Monotone drawings of planar graphs. J. Graph Theory, 46(1):39-47, 2004. URL: https://doi.org/10.1002/jgt.10168.
  29. André Schulz. Drawing 3-polytopes with good vertex resolution. J. Graph Algorithms Appl., 15(1):33-52, 2011. URL: https://doi.org/10.7155/jgaa.00216.
  30. Carsten Thomassen. Plane representations of graphs. In J. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 43-69. Academic Press, 1984. Google Scholar
  31. William T. Tutte. Convex representations of graphs. Proceedings of the London Mathematical Society, s3-10(1):304-320, 1960. URL: https://doi.org/10.1112/plms/s3-10.1.304.
  32. William T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 3(1):743-767, 1963. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact