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 -