Angelini, PatrizioBekos, Michael A.Förster, HenryGronemann, Martin2024-09-252024-09-252023Angelini, 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).https://doi.org/10.1007/s00453-023-01111-5https://hdl.handle.net/20.500.14490/325Bitonic 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.enAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/Upward planar graphsBitonic st-orderingsPlanar polyline drawingsBend minimizationArticle