On 1-Bend Upward Point-Set Embeddings of st-Digraphs
Publication date
2024
Authors
Di Giacomo, Emilio
Förster, Henry
Kokhovich, Daria
Mchedlidze, Tamara
Montecchiani, Fabrizio
Symvonis, Antonios
Villedieu, Anaïs
Editors
Soto, José A.
Wiese, Andreas
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
We study the upward point-set embeddability of digraphs on one-sided convex point sets with at most 1 bend per edge. We provide an algorithm to compute a 1-bend upward point-set embedding of outerplanar st-digraphs on arbitrary one-sided convex point sets. We complement this result by proving that for every n≥18 there exists a 2-outerplanar st-digraph G with n vertices and a one-sided convex point set S so that G does not admit a 1-bend upward point-set embedding on S.
Keywords
Taverne, Theoretical Computer Science, General Computer Science
Citation
Di Giacomo, E, Förster, H, Kokhovich, D, Mchedlidze, T, Montecchiani, F, Symvonis, A & Villedieu, A 2024, On 1-Bend Upward Point-Set Embeddings of st-Digraphs. in J A Soto & A Wiese (eds), LATIN 2024 : Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14578 LNCS, Springer, pp. 3-18, 16th Latin American Symposium on Theoretical Informatics, LATIN 2042, Puerto Varas, Chile, 18/03/24. https://doi.org/10.1007/978-3-031-55598-5_1, conference