Bitonic st-Orderings for Upward Planar Graphs: The Variable Embedding Setting
Autor(en): | Angelini, P. Bekos, M.A. Förster, H. Gronemann, M. |
Herausgeber: | Adler, I. Muller, H. |
Stichwörter: | Bend minimization; Bitonic st-orderings; Clustering algorithms; Drawing (graphics); Embeddings; Graph algorithms; Graph structures, Graph-drawing problem; Linear-time algorithms; Lower bounds; Optimization problems; Planar graph; Planar polyline drawings; Polyline; Upper Bound, Graph theory; Upward planar graphs | Erscheinungsdatum: | 2020 | Herausgeber: | Springer Science and Business Media Deutschland GmbH | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Volumen: | 12301 LNCS | Startseite: | 339 | Seitenende: | 351 | Zusammenfassung: | 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. © 2020, Springer Nature Switzerland AG. |
Beschreibung: | Conference of 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020 ; Conference Date: 24 June 2020 Through 26 June 2020; Conference Code:250339 |
ISBN: | 9783030604394 | ISSN: | 03029743 | DOI: | 10.1007/978-3-030-60440-0_27 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85093858597&doi=10.1007%2f978-3-030-60440-0_27&partnerID=40&md5=2f0003f69dbd417dea89a2cb7fa74414 |
Zur Langanzeige
Seitenaufrufe
4
Letzte Woche
0
0
Letzter Monat
0
0
geprüft am 01.06.2024