Document Open Access Logo

Ortho-Radial Drawing in Near-Linear Time

Author Yi-Jun Chang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.35.pdf
  • Filesize: 1.15 MB
  • 20 pages

Document Identifiers

Author Details

Yi-Jun Chang
  • National University of Singapore, Singapore

Cite As Get BibTex

Yi-Jun Chang. Ortho-Radial Drawing in Near-Linear Time. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.35

Abstract

An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing 1987), a simple combinatorial characterization of angle assignments that can be realized as bend-free orthogonal drawings was established, thereby allowing an orthogonal drawing to be described combinatorially by listing the angles of all corners. The characterization reduces the need to consider certain geometric aspects, such as edge lengths and vertex coordinates, and simplifies the task of graph drawing algorithm design.
Barth, Niedermann, Rutter, and Wolf (SoCG 2017) established an analogous combinatorial characterization for ortho-radial drawings, which are a generalization of orthogonal drawings to cylindrical grids. The proof of the characterization is existential and does not result in an efficient algorithm. Niedermann, Rutter, and Wolf (SoCG 2019) later addressed this issue by developing quadratic-time algorithms for both testing the realizability of a given angle assignment as an ortho-radial drawing without bends and constructing such a drawing.
In this paper, we improve the time complexity of these tasks to near-linear time. We establish a new characterization for ortho-radial drawings based on the concept of a good sequence. Using the new characterization, we design a simple greedy algorithm for constructing ortho-radial drawings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Graph drawing
  • ortho-radial drawing
  • topology-shape-metric framework

Metrics

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

Related Versions

References

  1. Michael J. Bannister, David Eppstein, and Joseph A. Simons. Inapproximability of orthogonal compaction. Journal of Graph Algorithms and Applications, 16(3):651-673, 2012. URL: https://doi.org/10.7155/jgaa.00263.
  2. Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.14.
  3. Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. A topology-shape-metrics framework for ortho-radial graph drawing. arXiv preprint, 2021. URL: https://arxiv.org/abs/2106.05734v1.
  4. Hannah Bast, Patrick Brosi, and Sabine Storandt. Metro maps on flexible base grids. In 17th International Symposium on Spatial and Temporal Databases, pages 12-22, 2021. Google Scholar
  5. Carlo Batini, Enrico Nardelli, and Roberto Tamassia. A layout algorithm for data flow diagrams. IEEE Transactions on Software Engineering, SE-12(4):538-546, 1986. Google Scholar
  6. Michael A. Bekos, Carla Binucci, Giuseppe Di Battista, Walter Didimo, Martin Gronemann, Karsten Klein, Maurizio Patrignani, and Ignaz Rutter. On turn-regular orthogonal representations. Journal of Graph Algorithms and Applications, 26(3):285-306, 2022. URL: https://doi.org/10.7155/jgaa.00595.
  7. Sandeep N Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28(2):300-343, 1984. Google Scholar
  8. Therese Biedl, Anna Lubiw, Mark Petrick, and Michael Spriggs. Morphing orthogonal planar graph drawings. ACM Transactions on Algorithms (TALG), 9(4):1-24, 2013. Google Scholar
  9. Thomas Bläsius, Ignaz Rutter, and Dorothea Wagner. Optimal orthogonal graph drawing with convex bend costs. ACM Trans. Algorithms, 12(3):33:1-33:32, 2016. Google Scholar
  10. Ulrik Brandes, Sabine Cornelsen, Christian Fieß, and Dorothea Wagner. How to draw the minimum cuts of a planar graph. Computational Geometry, 29(2):117-133, 2004. Google Scholar
  11. Ulrik Brandes and Dorothea Wagner. Dynamic grid embedding with few bends and changes. In International Symposium on Algorithms and Computation, pages 90-99. Springer, 1998. Google Scholar
  12. Stina S Bridgeman, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Roberto Tamassia, and Luca Vismara. Turn-regularity and optimal area drawings of orthogonal representations. Computational Geometry, 16(1):53-93, 2000. Google Scholar
  13. Yi-Jun Chang and Hsu-Chun Yen. On bend-minimized orthogonal drawings of planar 3-graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  14. Sabine Cornelsen and Andreas Karrenbauer. Accelerated bend minimization. JGAA, 16(3):635-650, 2012. Google Scholar
  15. Giuseppe Di Battista, Walter Didimo, Maurizio Patrignani, and Maurizio Pizzonia. Orthogonal and quasi-upward drawings with vertices of prescribed size. In Proceedings of the 7th International Symposium on Graph Drawing (GD), pages 297-310. Springer Berlin Heidelberg, 1999. Google Scholar
  16. Giuseppe Di Battista, Giuseppe Liotta, and Francesco Vargiu. Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6):1764-1811, 1998. Google Scholar
  17. Walter Didimo, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani. Optimal orthogonal drawings of planar 3-graphs in linear time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 806-825. SIAM, 2020. Google Scholar
  18. Walter Didimo, Giuseppe Liotta, and Maurizio Patrignani. On the complexity of HV-rectilinear planarity testing. In International Symposium on Graph Drawing (GD), pages 343-354. Springer, 2014. Google Scholar
  19. Walter Didimo, Giuseppe Liotta, and Maurizio Patrignani. Bend-minimum orthogonal drawings in quadratic time. In International Symposium on Graph Drawing and Network Visualization (GD), pages 481-494. Springer, 2018. Google Scholar
  20. Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. Nested dissection meets ipms: Planar min-cost flow in nearly-linear time. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 124-153. SIAM, 2022. Google Scholar
  21. Stephane Durocher, Stefan Felsner, Saeed Mehrabi, and Debajyoti Mondal. Drawing HV-restricted planar graphs. In Latin American Symposium on Theoretical Informatics (LATIN), pages 156-167. Springer, 2014. Google Scholar
  22. Markus Eiglsperger, Carsten Gutwenger, Michael Kaufmann, Joachim Kupke, Michael Jünger, Sebastian Leipert, Karsten Klein, Petra Mutzel, and Martin Siebenhaller. Automatic layout of UML class diagrams in orthogonal style. Information Visualization, 3(3):189-208, 2004. Google Scholar
  23. Martin Fink, Magnus Lechner, and Alexander Wolff. Concentric metro maps. In Proceedings of the Schematic Mapping Workshop (SMW), 2014. Google Scholar
  24. Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, and G Woeginger. Drawing graphs in the plane with high resolution. SIAM Journal on Computing, 22(5):1035-1052, 1993. Google Scholar
  25. Ashim Garg and Roberto Tamassia. A new minimum cost flow algorithm with applications to graph drawing. In Proceedings of the Symposium on Graph Drawing (GD), pages 201-216. Springer Berlin Heidelberg, 1997. Google Scholar
  26. Carsten Gutwenger, Michael Jünger, Karsten Klein, Joachim Kupke, Sebastian Leipert, and Petra Mutzel. A new approach for visualizing UML class diagrams. In Proceedings of the 2003 ACM symposium on Software visualization, pages 179-188, 2003. Google Scholar
  27. Mahdieh Hasheminezhad, S Mehdi Hashemi, Brendan D McKay, and Maryam Tahmasbi. Rectangular-radial drawings of cubic plane graphs. Computational Geometry, 43(9):767-780, 2010. Google Scholar
  28. Mahdieh Hasheminezhad, S Mehdi Hashemi, and Maryam Tahmasbi. Ortho-radial drawings of graphs. Australasian Journal of Combinatorics, 44:171-182, 2009. Google Scholar
  29. Min-Yu Hsueh. Symbolic layout and compaction of integrated circuits. PhD thesis, University of California, Berkeley, 1980. Google Scholar
  30. Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow. Hola: Human-like orthogonal network layout. IEEE transactions on visualization and computer graphics, 22(1):349-358, 2015. Google Scholar
  31. Gunnar W. Klau and Petra Mutzel. Quasi-orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, 1998. Google Scholar
  32. Gunnar W Klau and Petra Mutzel. Optimal compaction of orthogonal grid drawings. In Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 304-319. Springer, 1999. Google Scholar
  33. Robin S. Liggett and William J. Mitchell. Optimal space planning in practice. Computer-Aided Design, 13(5):277-288, 1981. Special Issue Design optimization. URL: https://doi.org/10.1016/0010-4485(81)90317-1.
  34. Benjamin Niedermann and Ignaz Rutter. An integer-linear program for bend-minimization in ortho-radial drawings. In International Symposium on Graph Drawing and Network Visualization, pages 235-249. Springer, 2020. Google Scholar
  35. Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1-53:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.53.
  36. Achilleas Papakostas and Ioannis G Tollis. Efficient orthogonal drawings of high degree graphs. Algorithmica, 26(1):100-125, 2000. Google Scholar
  37. Maurizio Patrignani. On the complexity of orthogonal compaction. Computational Geometry, 19(1):47-67, 2001. Google Scholar
  38. James A Storer. The node cost measure for embedding graphs on the planar grid. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 201-210, 1980. Google Scholar
  39. Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421-444, 1987. Google Scholar
  40. Leslie G Valiant. Universality considerations in VLSI circuits. IEEE Transactions on Computers, 100(2):135-140, 1981. Google Scholar
  41. Hsiang-Yun Wu, Benjamin Niedermann, Shigeo Takahashi, Maxwell J. Roberts, and Martin Nöllenburg. A survey on transit map layout - from design, machine, and human perspectives. Computer Graphics Forum, 39(3):619-646, 2020. URL: https://doi.org/10.1111/cgf.14030.
  42. Yingying Xu, Ho-Yin Chan, and Anthony Chen. Automated generation of concentric circles metro maps using mixed-integer optimization. International Journal of Geographical Information Science, pages 1-26, 2022. 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 About DROPS Imprint Privacy Contact