# Bryan T. Wilkinson

## Morphing Planar Graph Drawings with a Polynomial Number of Steps

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-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 language | English |
---|

Journal | The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings |
---|

Volume | 24 |
---|

Pages (from-to) | 1656-1667 |
---|

Number of pages | 12 |
---|

ISSN | 1071-9040 |
---|

Publication status | Published - 2013 |
---|

Event | ACM-SIAM symposium on Disrete Algorithms - New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 |
---|

Conference | ACM-SIAM symposium on Disrete Algorithms |
---|

Number | 24 |
---|

Country | United States |
---|

City | New Orleans |
---|

Period | 06/01/2013 → 08/01/2013 |
---|

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