2018/08/31 by Giordano Da Lozzo, Giuseppe Di Battista, Da Lozzo, Giordano +7
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1808.10826
Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018) The current version is the extended one
arxiv created 2018/10/12 · arxiv updated 2018/10/15
We prove that, given two topologically-equivalent upward planar straight-line drawings of an n-vertex directed graph G, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of O(1) morphing steps if G is a reduced planar st-graph, O(n) morphing steps if G is a planar st-graph, O(n) morphing steps if G is a reduced upward planar graph, and O(n2) morphing steps if G is a general upward planar graph. Further, we show that Ω(n) morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an n-vertex path.