Geometric $(1+\epsilon )$-Spanners with Few Crossings

Abstract

For $n$ points in the plane and $\epsilon >0$, we construct a $(1+\epsilon )$-spanner with $O(n/\epsilon )$ edges in which every edge has $\tilde{O}(1/{\epsilon }^3)$ crossings, the total number of crossings is $\tilde{O}(n/{\epsilon }^4)$, and the ratio between the lengths of any two crossing edges is $O(1/{\epsilon }^2)$. Our spanner construction substantially improves on the previous upper bound for the number of crossings in a $(1+\epsilon )$-spanner, and it is the first spanner construction that ensures $O(1)$ crossings per edge for any constant $\epsilon >0$. In contrast, we construct $n$ points in the plane for which every $(1+\epsilon )$-spanner has $\Omega (n/{\epsilon }^3)$ crossings, $n$ points for which every $(1+\epsilon )$-spanner has an edge with $\Omega (1/{\epsilon }^{5/2})$ crossings, and 4 points for which every $(1+\epsilon )$-spanner contains two crossing edges where one is $\Omega (1/\epsilon )$ times longer than the other.

arXiv comment25 pages, 16 figures. A preliminary version appeared in the Proceedings of the 34th International Symposium on Graph Drawing and Network Visualization (GD 2026)