Oriented Spanners

Kevin Buchin

doi:10.1007/s00453-025-01342-8

Oriented Spanners

2025-12-11

0

OA

AI

DOI：10.1007/s00453-025-01342-8

Original

Save

Abstract

En 中文

Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spannerG 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n<^>7)$$\end{document} time for n points, and a greedy algorithm that computes a 5-spanner in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n\log n)$$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t=7.2 \cdot t_g$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t_g$$\end{document} is an upper bound on the dilation of the greedy triangulation.

Keywords:

computational geometry

Spanner

Oriented graph

Greedy triangulation

Oriented Spanners

Abstract

Journal

Organization

Cited Papers