Given an n-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of O(n) steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns’ 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.
Alamdari, S., Angelini, P., Barrera Cruz, F., Chan, T.M., DA LOZZO, G., DI BATTISTA, G., et al. (2017). How to Morph Planar Graph Drawings. SIAM JOURNAL ON COMPUTING, 46(2), 824-852.
Titolo: | How to Morph Planar Graph Drawings |
Autori: | |
Data di pubblicazione: | 2017 |
Rivista: | |
Citazione: | Alamdari, S., Angelini, P., Barrera Cruz, F., Chan, T.M., DA LOZZO, G., DI BATTISTA, G., et al. (2017). How to Morph Planar Graph Drawings. SIAM JOURNAL ON COMPUTING, 46(2), 824-852. |
Abstract: | Given an n-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of O(n) steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns’ 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps. |
Handle: | http://hdl.handle.net/11590/316742 |
Appare nelle tipologie: | 1.1 Articolo in rivista |