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 [10.1137/16M1069171].

How to Morph Planar Graph Drawings

ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;DI BATTISTA, Giuseppe;FRATI, FABRIZIO;PATRIGNANI, Maurizio;ROSELLI, VINCENZO;
2017-01-01

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.
2017
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 [10.1137/16M1069171].
File in questo prodotto:
File Dimensione Formato  
SICOMP-Published.pdf

accesso aperto

Descrizione: Published version at https://epubs.siam.org/doi/10.1137/16M1069171 with doi 10.1137/16M1069171
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 2.27 MB
Formato Adobe PDF
2.27 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/316742
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 35
  • ???jsp.display-item.citation.isi??? 17
social impact