Oriented Spanners
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Oriented Spanners. / Buchin, Kevin; Gudmundsson, Joachim; Kalb, Antonia; Popov, Aleksandr; Rehs, Carolin; van Renssen, André; Wong, Sampson.
31st Annual European Symposium on Algorithms, ESA 2023. ed. / Inge Li Gortz; Martin Farach-Colton; Simon J. Puglisi; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 1-16 26 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Oriented Spanners
AU - Buchin, Kevin
AU - Gudmundsson, Joachim
AU - Kalb, Antonia
AU - Popov, Aleksandr
AU - Rehs, Carolin
AU - van Renssen, André
AU - Wong, Sampson
N1 - Publisher Copyright: © Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong.
PY - 2023
Y1 - 2023
N2 - Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in O(n8) time for n points, and a greedy algorithm that computes a 5-spanner in O(n log n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented O(1)-spanner.
AB - Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in O(n8) time for n points, and a greedy algorithm that computes a 5-spanner in O(n log n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented O(1)-spanner.
KW - computational geometry
KW - greedy triangulation
KW - oriented graph
KW - spanner
U2 - 10.4230/LIPIcs.ESA.2023.26
DO - 10.4230/LIPIcs.ESA.2023.26
M3 - Article in proceedings
AN - SCOPUS:85173532152
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 16
BT - 31st Annual European Symposium on Algorithms, ESA 2023
A2 - Li Gortz, Inge
A2 - Farach-Colton, Martin
A2 - Puglisi, Simon J.
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 31st Annual European Symposium on Algorithms, ESA 2023
Y2 - 4 September 2023 through 6 September 2023
ER -
ID: 382560406