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.
Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V. (2020). Upward Planar Morphs. ALGORITHMICA, 82(10), 2985-3017 [10.1007/s00453-020-00714-6].
Upward Planar Morphs
Da Lozzo G.;Di Battista G.;Frati F.;Patrignani M.;Roselli V.
2020-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
