TY - GEN

T1 - Morphing planar graph drawings with a polynomial number of steps

AU - Alamdari, Soroush

AU - Angelini, Patrizio

AU - Chan, Timothy M.

AU - Di Battista, Giuseppe

AU - Frati, Fabrizio

AU - Lubiw, Anna

AU - Patrignani, Maurizio

AU - Roselli, Vincenzo

AU - Singla, Sahil

AU - Wilkinson, Bryan T.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84876023163&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876023163&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973105.119

DO - 10.1137/1.9781611973105.119

M3 - Conference contribution

AN - SCOPUS:84876023163

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1656

EP - 1667

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -