2026-07-21T14:19:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18679 2024-03-12T12:01:30Z ddc:004 open_access

Oriented Spanners Buchin, Kevin Gudmundsson, Joachim Kalb, Antonia Popov, Aleksandr Rehs, Carolin van Renssen, André Wong, Sampson computational geometry spanner oriented graph greedy triangulation 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 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog 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 𝒪(1)-spanner. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Joachim Gudmundsson and Antonia Kalb and Aleksandr Popov and Carolin Rehs and André van Renssen and Sampson Wong 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.26 urn:nbn:de:0030-drops-186796 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode