Morphing planar graph drawings with a polynomial number of steps

Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n4) steps.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery
Pages1656-1667
Number of pages12
ISBN (Print)9781611972511
DOIs
StatePublished - Jan 1 2013
Externally publishedYes
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
CountryUnited States
CityNew Orleans, LA
Period1/6/131/8/13

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Morphing planar graph drawings with a polynomial number of steps'. Together they form a unique fingerprint.

  • Cite this

    Alamdari, S., Angelini, P., Chan, T. M., Di Battista, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V., Singla, S., & Wilkinson, B. T. (2013). Morphing planar graph drawings with a polynomial number of steps. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 1656-1667). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973105.119