@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 = "Funding Information: The second author was partially supported by DFG grant Ka812/17-1. The fourth and ninth authors were partially supported by NSERC, the Natural Sciences and Engineering Research Council of Canada. The fifth author was partially supported by the U.S. Defense Advanced Research Projects Agency (DARPA) under agreement AFRL FA8750-15-2-0092. The sixth, seventh, tenth, and eleventh authors were partially supported by H2020-MSCA-RISE project 73499 {"}CONNECT,{"} by MIUR project {"}AMANDA - Algorithmics for MAssive and Networked DAta,{"} 2012C4E3KT 001, and by MIUR project {"}MODE - MOrphing graph Drawings Efficiently,{"} 20157EFM5C 001. The eighth author was partially supported by NSERC, the Natural Sciences and Engineering Research Council of Canada. The thirteenth author was supported by the Danish National Research Foundation grant DNRF84 through the Center for Massive Data Algorithmics (MADALGO).",

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

}