Bryan T. Wilkinson

Morphing Planar Graph Drawings with a Polynomial Number of Steps

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Soroush Alamdari, University of Waterloo, Canada
  • Patrizio Angelini, Dipartimento di Informatica e Automazione, Universita' Roma Tre, Italy
  • Timothy M. Chan, School of Computer Science, University of Waterloo, Canada
  • Giuseppe Di Battista, Dipartimento di Informatica e Automazione, Universita' Roma Tre, Italy
  • Fabrizio Frati, Dipartimento di Informatica e Automazione, Universita' Roma Tre, Italy
  • Anna Lubiw, School of Computer Science, University of Waterloo, Canada
  • Maurizio Patrignani, Dipartimento di Informatica e Automazione, Universita' Roma Tre, Italy
  • Vincenzo Roselli, Dipartimento di Informatica e Automazione, Universita' Roma Tre, Italy
  • Sahil Singla
  • ,
  • Bryan Thomas Wilkinson
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(n^2) 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(n^4) steps.
Original languageEnglish
JournalThe Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings
Volume24
Pages (from-to)1656-1667
Number of pages12
ISSN1071-9040
Publication statusPublished - 2013
EventACM-SIAM symposium on Disrete Algorithms - New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
Conference number: 24

Conference

ConferenceACM-SIAM symposium on Disrete Algorithms
Number24
CountryUnited States
CityNew Orleans
Period06/01/201308/01/2013

Bibliographical note

Title of the vol.: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms
ISSN CD: 2160-1445. Online: 1557-9468
ISBN CD: 9781611972528

See relations at Aarhus University Citationformats

ID: 52754878