How to morph planar graph drawings

Soroush Alamdari; Patrizio Angelini; Fidel Barrera-Cruz; Timothy M. Chan; Giordano Da Lozzo; Giuseppe Di Battista; Fabrizio Frati; Penny Haxell; Anna Lubiw; Maurizio Patrignani; Vincenzo Roselli; Sahil Singla; Bryan T. Wilkinso

doi:10.1137/16M1069171

How to morph planar graph drawings

Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinso

Computer Science

Research output: Contribution to journal › Article › peer-review

36 Scopus citations

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.

Original language	English (US)
Pages (from-to)	824-852
Number of pages	29
Journal	SIAM Journal on Computing
Volume	46
Issue number	2
DOIs	https://doi.org/10.1137/16M1069171
State	Published - 2017

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Morph
Planar graphs
Transformation

Access to Document

10.1137/16M1069171

Cite this

@article{decdc2fe459543ae9558461b71db7ca1,

title = "How to morph planar graph drawings",

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.",

keywords = "Morph, Planar graphs, Transformation",

author = "Soroush Alamdari and Patrizio Angelini and Fidel Barrera-Cruz and Chan, {Timothy M.} and {Da Lozzo}, Giordano and {Di Battista}, Giuseppe and Fabrizio Frati and Penny Haxell and Anna Lubiw and Maurizio Patrignani and Vincenzo Roselli and Sahil Singla and Wilkinso, {Bryan T.}",

note = "Publisher Copyright: {\textcopyright} by SIAM 2017.",

year = "2017",

doi = "10.1137/16M1069171",

language = "English (US)",

volume = "46",

pages = "824--852",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - How to morph planar graph drawings

AU - Alamdari, Soroush

AU - Angelini, Patrizio

AU - Barrera-Cruz, Fidel

AU - Chan, Timothy M.

AU - Da Lozzo, Giordano

AU - Di Battista, Giuseppe

AU - Frati, Fabrizio

AU - Haxell, Penny

AU - Lubiw, Anna

AU - Patrignani, Maurizio

AU - Roselli, Vincenzo

AU - Singla, Sahil

AU - Wilkinso, Bryan T.

PY - 2017

Y1 - 2017

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

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

KW - Morph

KW - Planar graphs

KW - Transformation

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

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

U2 - 10.1137/16M1069171

DO - 10.1137/16M1069171

M3 - Article

AN - SCOPUS:85018402992

SN - 0097-5397

VL - 46

SP - 824

EP - 852

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

How to morph planar graph drawings

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this