Upward Planar Morphs

  • PDF / 4,200,783 Bytes
  • 33 Pages / 439.37 x 666.142 pts Page_size
  • 56 Downloads / 191 Views

DOWNLOAD

REPORT


Upward Planar Morphs Giordano Da Lozzo1 · Giuseppe Di Battista1 · Fabrizio Frati1   · Maurizio Patrignani1 · Vincenzo Roselli1 Received: 25 October 2018 / Accepted: 17 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020

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. Keywords  Graph drawing · Planar morph · Directed graph · Upward planarity

1 Introduction One of the definitions of the word morph that can be found in English dictionaries is “to gradually change into a different image”. The Graph Drawing community defines the morph of graph drawings similarly. Namely, given two drawings 𝛤0 and A preliminary version of this paper appeared in [17]. * Fabrizio Frati [email protected] Giordano Da Lozzo [email protected] Giuseppe Di Battista [email protected] Maurizio Patrignani [email protected] Vincenzo Roselli [email protected] 1



Roma Tre University, Rome, Italy

13

Vol.:(0123456789)

Algorithmica

𝛤1 of a graph G, a morph between 𝛤0 and 𝛤1 is a continuously changing family of drawings of G indexed by time t ∈ [0, 1] , such that the drawing at time t = 0 is 𝛤0 and the drawing at time t = 1 is 𝛤1 . Further, the way the Graph Drawing community adopted the word morph is consistent with its Ancient Greek root 𝜇𝜔𝜌𝜙𝜂́  , which means “shape” in a broad sense. Namely, if both 𝛤0 and 𝛤1 have a certain geometric property, it is desirable that all the drawings of the morph also have the same property. In particular, we talk about a planar, a straight-line, an orthogonal, or a convex morph if all the intermediate drawings of the morph are planar (edges do not cross), straight-line (edges are straight-line segments), orthogonal (edges are polygonal lines composed of horizontal and vertical segments), or convex (the drawings are planar and straight-line, and the faces are delimited by convex polygons), respectively. The state of the art on planar morphs covers more than 100 years, starting from the 1914/1917 works of Tietze [35] and Smith [31]. The seminal papers of Cairns [14] and Thomassen [34] proved the existence of a planar straight-line morph between any two topologically-equivalent planar straight-line drawings of a graph. In the last 10 years, the attention of the research community focused on algorithms for constructing planar morphs with few morphing steps (see, e.g., [1–8, 12, 13, 28, 36]). Each morphing step, sometimes simply c