Algorithmica Computer Science Applications

Oriented Spanners

Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, Sampson Wong
Springer Nature · 2025-12-11 · DOI 10.1007/s00453-025-01342-8

Abstract

Abstract Given a point set P in the Euclidean plane and a parameter t , we define an oriented t -spanner G as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest closed walk in G through those points is at most a factor t longer than the shortest cycle in the complete graph on P . 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 $$\mathcal {O}(n^7)$$ time for n points, and a greedy algorithm that computes a 5-spanner in $$\mathcal {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 a plane oriented t -spanner with $$t=7.2 \cdot t_g$$ , where $$t_g$$ is an upper bound on the dilation of the greedy triangulation.

Read at publisher →