Abstract
A hierarchical plane stgraph H can be thought of as a combinatorial description of a planar drawing Γ of a 2connected graph G in which each edge is a ymonotone curve and each face encloses a ymonotone region (that is, a region whose intersection with any horizontal line is a line segment, a point, or empty). A drawing Γ' of H is a drawing of G such that each horizontal line intersects the same lefttoright order of edges and vertices in Γ and Γ', that is, the underlying hierarchical plane stgraph of both drawings is H. A straightline planar drawing of a graph is convex if the boundary of each face is realized as a convex polygon.
We study the computation of convex drawings of hierarchical plane stgraphs such that the outer face is realized as a prescribed polygon. Chrobak, Goodrich, and Tamassia [SoCG'96] and, independently, Kleist et al. [CGTA'19] described an idea to solve this problem in O(n^{1.1865}) time, where n is the number of vertices of the graph. Also independently, Hong and Nagamochi [J. Discrete Algorithms'10] described a completely different approach, which can be executed in O(n²) time.
In this paper, we present an optimal O(n) time algorithm to solve the above problem, thereby improving the previous results by Chrobak, Goodrich, and Tamassia, Kleist et al., and by Hong and Nagamochi. Our result has applications in graph morphing. A planar morph is a continuous deformation of a graph drawing that preserves straightline planarity. We show that our algorithm can be used as a dropin replacement to speed up a procedure by Alamdari et al. [SICOMP'17] to morph between any two given straightline planar drawings of the same plane graph. The running time improves from O(n^{2.1865}) to O(n²log n). To obtain our results, we devise a new strategy for computing socalled archfree paths in hierarchical plane stgraphs, which might be of independent interest.
BibTeX  Entry
@InProceedings{klemz:LIPIcs.ESA.2021.57,
author = {Klemz, Boris},
title = {{Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {57:157:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14638},
URN = {urn:nbn:de:0030drops146381},
doi = {10.4230/LIPIcs.ESA.2021.57},
annote = {Keywords: convex drawing, hierarchical graph, graph drawing, computational geometry, planarity, planar graph, morphing, convexity}
}
Keywords: 

convex drawing, hierarchical graph, graph drawing, computational geometry, planarity, planar graph, morphing, convexity 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 