Oriented Spanners
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 822 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 31st Annual European Symposium on Algorithms, ESA 2023 |
Redaktører | Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman |
Forlag | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publikationsdato | 2023 |
Sider | 1-16 |
Artikelnummer | 26 |
ISBN (Elektronisk) | 9783959772952 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Holland Varighed: 4 sep. 2023 → 6 sep. 2023 |
Konference
Konference | 31st Annual European Symposium on Algorithms, ESA 2023 |
---|---|
Land | Holland |
By | Amsterdam |
Periode | 04/09/2023 → 06/09/2023 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 274 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Aleksandr Popov: Supported by the Dutch Research Council (NWO) under the project number 612.001.801.
Funding Information:
Supported by the Dutch Research Council (NWO) under the project
Publisher Copyright:
© Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong.
ID: 382560406