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

23 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 - 2013
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
Country/TerritoryUnited States
CityNew Orleans, LA
Period1/6/131/8/13

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

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