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 d≥3 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(k1−1/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(τn1−1/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(n1−1d); 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((n1−1d)+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.