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

Buchin, K, Gudmundsson, J, Kalb, A, Popov, A, Rehs, C, van Renssen, A & Wong, S 2023, Oriented Spanners. in I Li Gortz, M Farach-Colton, SJ Puglisi & G Herman (eds), 31st Annual European Symposium on Algorithms, ESA 2023., 26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 274, pp. 1-16, 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, Netherlands, 04/09/2023. https://doi.org/10.4230/LIPIcs.ESA.2023.26

APA

Buchin, K., Gudmundsson, J., Kalb, A., Popov, A., Rehs, C., van Renssen, A., & Wong, S. (2023). Oriented Spanners. In I. Li Gortz, M. Farach-Colton, S. J. Puglisi, & G. Herman (Eds.), 31st Annual European Symposium on Algorithms, ESA 2023 (pp. 1-16). [26] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Vol. 274 https://doi.org/10.4230/LIPIcs.ESA.2023.26

Vancouver

Buchin K, Gudmundsson J, Kalb A, Popov A, Rehs C, van Renssen A et al. Oriented Spanners. In Li Gortz I, Farach-Colton M, Puglisi SJ, Herman G, editors, 31st Annual European Symposium on Algorithms, ESA 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 1-16. 26. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274). https://doi.org/10.4230/LIPIcs.ESA.2023.26

Author

Buchin, Kevin ; Gudmundsson, Joachim ; Kalb, Antonia ; Popov, Aleksandr ; Rehs, Carolin ; van Renssen, André ; Wong, Sampson. / Oriented Spanners. 31st Annual European Symposium on Algorithms, ESA 2023. editor / Inge Li Gortz ; Martin Farach-Colton ; Simon J. Puglisi ; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 1-16 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274).

Bibtex

@inproceedings{f31ae0d3d8424f3db733cc99bc2c0c3d,
title = "Oriented Spanners",
abstract = "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.",
keywords = "computational geometry, greedy triangulation, oriented graph, spanner",
author = "Kevin Buchin and Joachim Gudmundsson and Antonia Kalb and Aleksandr Popov and Carolin Rehs and {van Renssen}, Andr{\'e} and Sampson Wong",
note = "Publisher Copyright: {\textcopyright} Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, Andr{\'e} van Renssen, and Sampson Wong.; 31st Annual European Symposium on Algorithms, ESA 2023 ; Conference date: 04-09-2023 Through 06-09-2023",
year = "2023",
doi = "10.4230/LIPIcs.ESA.2023.26",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "1--16",
editor = "{Li Gortz}, Inge and Martin Farach-Colton and Puglisi, {Simon J.} and Grzegorz Herman",
booktitle = "31st Annual European Symposium on Algorithms, ESA 2023",

}

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