Bitonic st-Orderings for Upward Planar Graphs: The Variable Embedding Setting
Angelini, Patrizio
Bekos, Michael A. Förster, Henry Gronemann, Martin
Bekos, Michael A.
Förster, Henry
Gronemann, Martin
Citations
Altmetric:
Abstract
Bitonic st-orderings for st-planar graphs were recently introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the best-known upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge. For an st-planar graph that does not admit a bitonic st-ordering, one may split certain edges such that for the resulting graph such an ordering exists. Since each split is interpreted as a bend, one is usually interested in splitting as few edges as possible. While this optimization problem admits a linear-time algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a linear-time algorithm that optimizes over all embeddings of the input st-planar graph. The best-known lower bound on the number of required splits of an st-planar graph with n vertices is n - 3 . However, it is possible to compute a bitonic st-ordering without any split for the st-planar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings, the former translates into n - 3 bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an st-planar graph that needs at least n - 5 splits in both orientations.
Description
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Upward planar graphs, Bitonic st-orderings, Planar polyline drawings, Bend minimization
Citation
Angelini, Patrizio, Michael A. Bekos, Henry Förster, Martin Gronemann. “Bitonic st-Orderings for Upward Planar Graphs: The Variable Embedding Setting”. In Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers, 339-351. Cham, Switzerland: Springer. 2020.