Greedy Spanners in Euclidean Spaces Admit Sublinear Separators

Published in SODA, 2022

Recommended citation: H Le, C Than. (2021). "Greedy Spanners in Euclidean Spaces Admit Sublinear Separators ." The 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA22).

The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh showed that the greedy spanner in R2 admits a sublinear separator in a strong sense: any subgraph of k vertices of the greedy spanner in R2 has a separator of size O(k). Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in Rd for any constant d3 as an open problem.

In this paper, we resolve the problem of Eppstein and Khodabandeh by showing that any subgraph of k vertices of the greedy spanner in Rd has a separator of size O(k11/d). We introduce a new technique that gives a simple characterization for any geometric graph to have a sublinear separator that we dub \emph{τ-lanky}: a geometric graph is τ-lanky if any ball of radius r cuts at most τ edges of length at least r in the graph. We show that any τ-lanky geometric graph of n vertices in Rd has a separator of size O(τn11/d). We then derive our main result by showing that the greedy spanner is O(1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in Rd.

Our technique naturally extends to doubling metrics. We use the τ-lanky characterization to show that there exists a (1+ϵ)-spanner for doubling metrics of dimension d with a constant maximum degree and a separator of size O(n11d); this result resolves an open problem posed by Abam and Har-Peled a decade ago. We then introduce another simple characterization for a graph in doubling metrics of dimension d to have a sublinear separator. We use the new characterization to show that the greedy spanner of an n-point metric space of doubling dimension d has a separator of size O((n11d)+logΔ) where Δ is the spread of the metric; the factor log(Δ) is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has \emph{unbounded maximum degree}. Finally, we discuss algorithmic implications of our results.

Download paper here