Optimal Morphs of Planar Orthogonal Drawings

Authors Arthur van Goethem, Kevin Verbeek



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.42.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Arthur van Goethem
Kevin Verbeek

Cite AsGet BibTex

Arthur van Goethem and Kevin Verbeek. Optimal Morphs of Planar Orthogonal Drawings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.42

Abstract

We describe an algorithm that morphs between two planar orthogonal drawings Gamma_I and Gamma_O of a connected graph G, while preserving planarity and orthogonality. Necessarily Gamma_I and Gamma_O share the same combinatorial embedding. Our morph uses a linear number of linear morphs (linear interpolations between two drawings) and preserves linear complexity throughout the process, thereby answering an open question from Biedl et al. [Biedl et al., 2013]. Our algorithm first unifies the two drawings to ensure an equal number of (virtual) bends on each edge. We then interpret bends as vertices which form obstacles for so-called wires: horizontal and vertical lines separating the vertices of Gamma_O. We can find corresponding wires in Gamma_I that share topological properties with the wires in Gamma_O. The structural difference between the two drawings can be captured by the spirality of the wires in Gamma_I, which guides our morph from Gamma_I to Gamma_O.
Keywords
  • Homotopy
  • Morphing
  • Orthogonal drawing
  • Spirality

Metrics

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

References

  1. Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, and Bryan Wilkinson. How to morph planar graph drawings. SIAM Journal on Computing, 46(2):824-852, 2017. Google Scholar
  2. Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmović, Fabrizio Frati, and Pat Morin. Compatible connectivity augmentation of planar disconnected graphs. Discrete & Computational Geometry, 54(2):459-480, 2015. Google Scholar
  3. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. Morphing planar graph drawings efficiently. In Proc. 21st International Symposium on Graph Drawing, pages 49-60, 2013. Google Scholar
  4. Therese Biedl, Anna Lubiw, Mark Petrick, and Michael Spriggs. Morphing orthogonal planar graph drawings. ACM Transactions on Algorithms, 9(4):29:1-29:24, 2013. Google Scholar
  5. Therese Biedl, Anna Lubiw, and Michael Spriggs. Morphing planar graphs while preserving edge directions. In Proc. 13th International Symposium on Graph Drawing, pages 13-24, 2006. Google Scholar
  6. Thomas Bläsius, Sebastian Lehmann, and Ignaz Rutter. Orthogonal graph drawing with inflexible edges. Computational Geometry, 55:26-40, 2016. Google Scholar
  7. Steward Cairns. Deformations of plane rectilinear complexes. The American Mathematical Monthly, 51(5):247-252, 1944. Google Scholar
  8. Giuseppe Di Battista, Giuseppe Liotta, and Francesco Vargiu. Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6):1764-1811, 1998. Google Scholar
  9. Walter Didimo, Francesco Giordano, and Giuseppe Liotta. Upward spirality and upward planarity testing. SIAM Journal on Discrete Mathematics, 23(4):1842-1899, 2009. Google Scholar
  10. Michael Freedman, Joel Hass, and Peter Scott. Closed geodesics on surfaces. Bulletin of the London Mathematical Society, 14(5):385-391, 1982. Google Scholar
  11. Bettina Speckmann and Kevin Verbeek. Homotopic c-oriented routing with few links and thick edges. Computational Geometry, 67:11-28, 2018. Google Scholar
  12. Carsten Thomassen. Deformations of plane graphs. Journal of Combinatorial Theory, Series B, 34(3):244-257, 1983. 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