Document Open Access Logo

Optimal Morphs of Convex Drawings

Authors Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.126.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Patrizio Angelini
Giordano Da Lozzo
Fabrizio Frati
Anna Lubiw
Maurizio Patrignani
Vincenzo Roselli

Cite As Get BibTex

Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, and Vincenzo Roselli. Optimal Morphs of Convex Drawings. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 126-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.126

Abstract

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.

Subject Classification

Keywords
  • Convex Drawings
  • Planar Graphs
  • Morphing
  • Geometric Representations

Metrics

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

References

  1. S. Alamdari, P. Angelini, T. M. Chan, G. Di Battista, F. Frati, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, and B. T. Wilkinson. Morphing planar graph drawings with a polynomial number of steps. In SODA, pages 1656-1667, 2013. Google Scholar
  2. G. Aloupis, L. Barba, P. Carmi, V. Dujmovic, F. Frati, and P. Morin. Compatible connectivity-augmentation of planar disconnected graphs. In SODA, pages 1602-1615, 2015. Google Scholar
  3. P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, and V. Roselli. Morphing planar graph drawings optimally. In ICALP, volume 8572 of LNCS, pages 126-137, 2014. Google Scholar
  4. P. Angelini, F. Frati, M. Patrignani, and V. Roselli. Morphing planar graph drawings efficiently. In GD, volume 8242 of LNCS, pages 49-60, 2013. Google Scholar
  5. I. Bárány and G. Rote. Strictly convex drawings of planar graphs. Documenta Mathematica, 11:369-391, 2006. Google Scholar
  6. D. Barnette and B. Grünbaum. On Steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs. In Many Facets of Graph Theory, volume 110 of Lecture Notes in Mathematics, pages 27-40. Springer, 1969. Google Scholar
  7. F. Barrera-Cruz, P. Haxell, and A. Lubiw. Morphing planar graph drawings with unidirectional moves. Mexican Conference on Discr. Math. and Comput. Geom., 2013. Google Scholar
  8. N. Bonichon, S. Felsner, and M. Mosbah. Convex drawings of 3-connected plane graphs. Algorithmica, 47(4):399-420, 2007. Google Scholar
  9. S. Cairns. Deformations of plane rectilinear complexes. Am. Math. Mon., 51:247-252, 1944. Google Scholar
  10. N. Chiba, T. Yamanouchi, and T. Nishizeki. Linear algorithms for convex drawings of planar graphs. In Progress in Graph Theory, pages 153-173. Academic Press, New York, NY, 1984. Google Scholar
  11. M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geometry Appl., 7(3):211-223, 1997. Google Scholar
  12. C. Erten, S. G. Kobourov, and C. Pitta. Intersection-free morphing of planar graphs. In GD, volume 2912 of LNCS, pages 320-331, 2004. Google Scholar
  13. C. Friedrich and P. Eades. Graph drawing in motion. J. Graph Alg. Ap., 6:353-370, 2002. Google Scholar
  14. C. Gotsman and V. Surazhsky. Guaranteed intersection-free polygon morphing. Computers & Graphics, 25(1):67-75, 2001. Google Scholar
  15. B. Grunbaum and G.C. Shephard. The geometry of planar graphs. Camb. Univ. Pr., 1981. Google Scholar
  16. S. H. Hong and H. Nagamochi. Convex drawings of hierarchical planar graphs and clustered planar graphs. J. Discrete Algorithms, 8(3):282-295, 2010. Google Scholar
  17. S. H. Hong and H. Nagamochi. A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs. Algorithmica, 58(2):433-460, 2010. Google Scholar
  18. M. S. Rahman, S. I. Nakano, and T. Nishizeki. Rectangular grid drawings of plane graphs. Comput. Geom., 10(3):203-220, 1998. Google Scholar
  19. M. S. Rahman, T. Nishizeki, and S. Ghosh. Rectangular drawings of planar graphs. J. of Algorithms, 50:62-78, 2004. Google Scholar
  20. J. M. Schmidt. Contractions, removals, and certifying 3-connectivity in linear time. SIAM J. Comput., 42(2):494-535, 2013. Google Scholar
  21. V. Surazhsky and C. Gotsman. Controllable morphing of compatible planar triangulations. ACM Trans. Graph, 20(4):203-231, 2001. Google Scholar
  22. V. Surazhsky and C. Gotsman. Intrinsic morphing of compatible triangulations. Internat. J. of Shape Model., 9:191-201, 2003. Google Scholar
  23. C. Thomassen. Planarity and duality of finite and infinite graphs. J. Comb. Theory, Ser. B, 29(2):244-271, 1980. Google Scholar
  24. C. Thomassen. Deformations of plane graphs. J. Comb. Th. Ser. B, 34(3):244-257, 1983. Google Scholar
  25. C. Thomassen. Plane representations of graphs. In J. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 43-69. Academic Press, New York, NY, 1984. 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