On 1-Bend Upward Point-Set Embeddings of st-Digraphs

Emilio Di Giacomo; Henry Förster; Daria Kokhovich; Tamara Mchedlidze; Fabrizio Montecchiani; Antonios Symvonis; Anaïs Villedieu

doi:10.1007/978-3-031-55598-5_1

On 1-Bend Upward Point-Set Embeddings of st-Digraphs

Emilio Di Giacomo^*, Henry Förster, Daria Kokhovich, Tamara Mchedlidze, Fabrizio Montecchiani, Antonios Symvonis, Anaïs Villedieu

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	LATIN 2024
Subtitle of host publication	Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings
Editors	José A. Soto, Andreas Wiese
Publisher	Springer
Pages	3-18
ISBN (Print)	9783031555978
DOIs	https://doi.org/10.1007/978-3-031-55598-5_1
Publication status	Published - 2024
Event	16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, Chile Duration: 18 Mar 2024 → 22 Mar 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14578 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th Latin American Symposium on Theoretical Informatics, LATIN 2042
Country/Territory	Chile
City	Puerto Varas
Period	18/03/24 → 22/03/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Access to Document

10.1007/978-3-031-55598-5_1

978-3-031-55598-5_1Final published version, 410 KBLicence: Taverne

Cite this

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 (pp. 3-18). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14578 LNCS). Springer. https://doi.org/10.1007/978-3-031-55598-5_1

Di Giacomo, Emilio ; Förster, Henry ; Kokhovich, Daria et al. / On 1-Bend Upward Point-Set Embeddings of st-Digraphs. LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings. editor / José A. Soto ; Andreas Wiese. Springer, 2024. pp. 3-18 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8858bf20ccd24fa7951815641fa410d2,

title = "On 1-Bend Upward Point-Set Embeddings of st-Digraphs",

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.",

author = "\{Di Giacomo\}, Emilio and Henry F{\"o}rster and Daria Kokhovich and Tamara Mchedlidze and Fabrizio Montecchiani and Antonios Symvonis and Ana{\"i}s Villedieu",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 16th Latin American Symposium on Theoretical Informatics, LATIN 2042 ; Conference date: 18-03-2024 Through 22-03-2024",

year = "2024",

doi = "10.1007/978-3-031-55598-5\_1",

language = "English",

isbn = "9783031555978",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "3--18",

editor = "Soto, \{Jos{\'e} A.\} and Andreas Wiese",

booktitle = "LATIN 2024",

}

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 JA 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

On 1-Bend Upward Point-Set Embeddings of st-Digraphs. / Di Giacomo, Emilio; Förster, Henry; Kokhovich, Daria et al.
LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings. ed. / José A. Soto; Andreas Wiese. Springer, 2024. p. 3-18 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14578 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On 1-Bend Upward Point-Set Embeddings of st-Digraphs

AU - Di Giacomo, Emilio

AU - Förster, Henry

AU - Kokhovich, Daria

AU - Mchedlidze, Tamara

AU - Montecchiani, Fabrizio

AU - Symvonis, Antonios

AU - Villedieu, Anaïs

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85188726386

U2 - 10.1007/978-3-031-55598-5_1

DO - 10.1007/978-3-031-55598-5_1

M3 - Conference contribution

AN - SCOPUS:85188726386

SN - 9783031555978

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 18

BT - LATIN 2024

A2 - Soto, José A.

A2 - Wiese, Andreas

PB - Springer

T2 - 16th Latin American Symposium on Theoretical Informatics, LATIN 2042

Y2 - 18 March 2024 through 22 March 2024

ER -

Di Giacomo E, Förster H, Kokhovich D, Mchedlidze T, Montecchiani F, Symvonis A et al. On 1-Bend Upward Point-Set Embeddings of st-Digraphs. In Soto JA, Wiese A, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings. Springer. 2024. p. 3-18. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-55598-5_1