Upward Planar Morphs

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

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2020-10, Vol.82 (10), p.2985-3017
Main Authors: Da Lozzo, Giordano, Di Battista, Giuseppe, Frati, Fabrizio, Patrignani, Maurizio, Roselli, Vincenzo
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Equivalence
Graph theory
Mathematics of Computing
Morphing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ( n 2 ) 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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-020-00714-6