Graph parameters bound the quality of geometric spanners in Euclidean space
On (Directed) Width-Parameters of Geometric Spanners
Computational Geometry
Summary
Finding shortcuts between points in space can speed up many computer tasks, but some shortcuts make routes longer than the direct path between points. This paper studies how certain graph properties limit how close these shortcuts can be to the shortest paths. The authors found exact trade-offs between these graph features and the quality of the shortcuts. They also show that for one of these properties, called tree-depth, it’s very hard to find good shortcuts efficiently. Their results apply to both undirected and directed networks.
What this means in practice
- •For network engineers: Design communication networks with controlled complexity while ensuring signals travel nearly shortest routes based on geometric constraints.
- •For geospatial software developers: Implement spatial data structures with guarantees on approximation quality and structural parameters to improve route computations in mapping applications.
A theory result. No direct application yet.
Authors
Kevin Buchin, Carolin Rehs, Torben Scheele
Abstract
To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.