Loading...
Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario
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 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 in polynomial area. 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 stplanar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings in polynomial area, 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. We provide analogous bounds for graphs with small degree. Finally, we further investigate the relationship between splits in bitonic st-orderings and bends in upward planar polyline drawings with polynomial area, by providing bounds on the number of bends in such drawings.
Description
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
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, and Martin Gronemann. Bitonic st-Orderings for Upward Planar Graphs: Splits and Bends in the Variable Embedding Scenario. Algorithmica 85, 2667–2692 (2023).