Document Open Access Logo

Efficient Algorithms for Ortho-Radial Graph Drawing

Authors Benjamin Niedermann , Ignaz Rutter , Matthias Wolf

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.53.pdf
  • Filesize: 1.35 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin Niedermann
  • University of Bonn, Germany
Ignaz Rutter
  • University of Passau, Germany
Matthias Wolf
  • Karlsruhe Institute of Technology, Germany

Funding

  • Wolf, Matthias: Matthias Wolf was funded by the Helmholtz Program Storage and Cross-linked Infrastructures, Topic 6 Superconductivity, Networks and System Integration.

Cite As Get BibTex

Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.53

Abstract

Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths.
Barth et al. [2017] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation.
In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph Drawing
  • Ortho-Radial Graph Drawing
  • Ortho-Radial Representation
  • Topology-Shape-Metrics
  • Efficient Algorithms

Metrics

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

Related Versions

References

  1. Md. Jawaherul Alam, Stephen G. Kobourov, and Debajyoti Mondal. Orthogonal layout with optimal face complexity. Computational Geometry, 63:40-52, 2017. Google Scholar
  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, Computational Geometry (SoCG'17), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  3. Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings. CoRR, arXiv:1703.06040, 2017. URL: http://arxiv.org/abs/1703.06040.
  4. 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
  5. P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 49(8):826-840, 2000. Google Scholar
  6. 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
  7. Therese Biedl. New lower bounds for orthogonal graph drawings. In Franz J. Brandenburg, editor, Graph Drawing (GD'96), Lecture Notes of Computer Science, pages 28-39. Springer Berlin Heidelberg, 1996. Google Scholar
  8. Therese Biedl and Goos Kant. A better heuristic for orthogonal graph drawings. Computational Geometry, 9(3):159-180, 1998. Google Scholar
  9. Therese C. Biedl, Brendan P. Madden, and Ioannis G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In Giuseppe DiBattista, editor, Graph Drawing (GD'97), Lecture Notes in Computer Science, pages 391-402. Springer Berlin Heidelberg, 1997. Google Scholar
  10. Thomas Bläsius, Ignaz Rutter, and Dorothea Wagner. Optimal orthogonal graph drawing with convex bend costs. ACM Transactions on Algorithms, 12(3):33, 2016. Google Scholar
  11. Thomas Bläsius, Sebastian Lehmann, and Ignaz Rutter. Orthogonal graph drawing with inflexible edges. Computational Geometry, 55:26-40, 2016. Google Scholar
  12. Yi-Jun Chang and Hsu-Chun Yen. On Bend-Minimized Orthogonal Drawings of Planar 3-Graphs. In Boris Aronov and Matthew J. Katz, editors, Computational Geometry (SoCG'17), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  13. Sabine Cornelsen and Andreas Karrenbauer. Accelerated Bend Minimization. In Marc van Kreveld and Bettina Speckmann, editors, Graph Drawing (GD'12), Lecture Notes of Computer Science, pages 111-122. Springer Berlin Heidelberg, 2012. Google Scholar
  14. 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
  15. Markus Eiglsperger, Michael Kaufmann, and Martin Siebenhaller. A Topology-shape-metrics Approach for the Automatic Layout of UML Class Diagrams. In Software Visualization (SoftVis'03), pages 189-ff. ACM, 2003. Google Scholar
  16. Stefan Felsner, Michael Kaufmann, and Pavel Valtr. Bend-optimal orthogonal graph drawing in the general position model. Computational Geometry, 47(3, Part B):460-468, 2014. Special Issue on the 28th European Workshop on Computational Geometry (EuroCG 2012). Google Scholar
  17. Martin Fink, Herman Haverkort, Martin Nöllenburg, Maxwell Roberts, Julian Schuhmann, and Alexander Wolff. Drawing Metro Maps Using Bézier Curves. In W Didimo and M Patrignani, editors, Graph Drawing (GD'13), Lecture Notes in Computer Science, pages 463-474. Springer International Publishing, 2013. Google Scholar
  18. Ulrich Fößmeier and Michael Kaufmann. Drawing high degree graphs with low bend numbers. In Franz J. Brandenburg, editor, Graph Drawing (GD'96), Lecture Notes in Computer Science, pages 254-266. Springer Berlin Heidelberg, 1996. Google Scholar
  19. Carsten Gutwenger, Michael Jünger, Karsten Klein, Joachim Kupke, Sebastian Leipert, and Petra Mutzel. A New Approach for Visualizing UML Class Diagrams. In Symposium on Software Visualization (SoftVis'03), pages 179-188, New York, NY, USA, 2003. ACM. Google Scholar
  20. Madieh Hasheminezhad, S. Mehdi Hashemi, Brendan D. McKay, and Maryam Tahmasbi. Rectangular-Radial Drawings of Cubic Plane Graphs. Computational Geometry: Theory and Applications, 43:767-780, 2010. Google Scholar
  21. Madieh Hasheminezhad, S. Mehdi Hashemi, and Maryam Tahmasbi. Ortho-radial drawings of graphs. Australasian Journal of Combinatorics, 44:171-182, 2009. Google Scholar
  22. Seok-Hee Hong, Damian Merrick, and Hugo A. D. do Nascimento. Automatic Visualisation of Metro Maps. Journal of Visual Languages and Computing, 17(3):203-224, 2006. Google Scholar
  23. S. Kieffer, T. Dwyer, K. Marriott, and M. Wybrow. HOLA: Human-like Orthogonal Network Layout. IEEE Transactions on Visualization and Computer Graphics, 22(1):349-358, 2016. Google Scholar
  24. Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. CoRR, arXiv:1903.05048, 2019. URL: http://arxiv.org/abs/1903.05048.
  25. Martin Nöllenburg and Alexander Wolff. Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. Transactions on Visualization and Computer Graphics, 17(5):626-641, 2011. Google Scholar
  26. Achilleas Papakostas and Ioannis G. Tollis. Algorithms for area-efficient orthogonal drawings. Computational Geometry, 9(1):83-110, 1998. Google Scholar
  27. Ulf Rüegg, Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow. Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports. In Christian Duncan and Antonios Symvonis, editors, Graph Drawing (GD'14), Lecture Notes in Computer Science, pages 319-330. Springer Berlin Heidelberg, 2014. Google Scholar
  28. R. Tamassia. On Embedding a Graph in the Grid with the Minimum Number of Bends. Journal on Computing, 16(3):421-444, 1987. Google Scholar
  29. Roberto Tamassia, Giuseppe Di Battista, and Carlo Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man, and Cybernetics, 18(1):61-79, 1988. Google Scholar
  30. Roberto Tamassia, Ioannis G. Tollis, and Jeffrey Scott Vitter. Lower bounds for planar orthogonal drawings of graphs. Information Processing Letters, 39(1):35-40, 1991. Google Scholar
  31. L. G. Valiant. Universality considerations in VLSI circuits. IEEE Transactions on Computers, 30(02):135-140, 1981. Google Scholar
  32. Yu-Shuen Wang and Ming-Te Chi. Focus+Context Metro Maps. Transactions on Visualization and Computer Graphics, 17(12):2528-2535, 2011. Google Scholar
  33. Michael Wybrow, Kim Marriott, and Peter J. Stuckey. Orthogonal Connector Routing. In David Eppstein and Emden R. Gansner, editors, Graph Drawing (GD'10), Lecture Notes in Computer Science, pages 219-231. Springer Berlin Heidelberg, 2010. 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