Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.5555/2627817.2627936 | SODA |
Keywords | Field | DocType |
algorithms,design,nonnumerical algorithms and problems,complexity measures and classes,graph algorithms,theory | Discrete mathematics,Morphing,Line (geometry),Combinatorics,Embedding,Planarity testing,Vertex (geometry),Planar straight-line graph,Triangulation (social science),Mathematics,Planar graph | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 10 | 0.72 |
References | Authors | |
28 | 10 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Soroush Alamdari | 1 | 56 | 5.93 |
| Patrizio Angelini | 2 | 158 | 25.43 |
| Timothy M. Chan | 3 | 2033 | 150.55 |
| Giuseppe Di Battista | 4 | 2298 | 361.48 |
| Fabrizio Frati | 5 | 462 | 48.60 |
| Anna Lubiw | 6 | 753 | 95.36 |
| Maurizio Patrignani | 7 | 675 | 61.47 |
| Vincenzo Roselli | 8 | 69 | 11.57 |
| Sahil Singla | 9 | 83 | 16.29 |
| Bryan T. Wilkinson | 10 | 43 | 4.18 |