# Greedy Spanners in Euclidean Spaces Admit Sublinear Separators

@article{Le2021GreedySI, title={Greedy Spanners in Euclidean Spaces Admit Sublinear Separators}, author={Hung Le and Cuong V. Than}, journal={ArXiv}, year={2021}, volume={abs/2107.06490} }

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 [EK21] showed that the greedy spanner in R admits a sublinear separator in a strong sense: any subgraph of k vertices of the greedy spanner in R has a separator of size O( √ k). Their technique is… Expand

#### References

SHOWING 1-10 OF 68 REFERENCES

Euclidean spanners: short, thin, and lanky

- Mathematics, Computer Science
- STOC '95
- 1995

It is shown that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, Saarbrucken, Germany. Expand

The Greedy Spanner is Existentially Optimal

- Mathematics, Computer Science
- PODC
- 2016

It is concluded that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Expand

Optimal euclidean spanners: really short, thin and lanky

- Computer Science, Mathematics
- STOC '13
- 2013

This paper resolves the long-standing conjecture of Arya et al. that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time, and demonstrates that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics. Expand

Truly Optimal Euclidean Spanners

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

It is shown that any (1+ε) -spanner must have lightness Ω(ε^-d), and the upper bound on the lightness of the greedy spanner is improved, implying that the greedy (and other) spanners achieve the optimal size. Expand

Spanners for geometric intersection graphs with applications

- Mathematics, Computer Science
- J. Comput. Geom.
- 2012

The first algorithm for constructing spanners of ball graphs is presented, using an efficient subdivision of space to construct a sparse graph having many of the same distance properties as the input ball graph, and the constructed spanners have a small vertex separator decomposition (hereditary). Expand

A Light Metric Spanner

- Mathematics, Computer Science
- 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- 2015

This paper shows that doubling spaces admit (1 + ε)-stretch spanners with lightness WD = (ddim /ε)<sup>O(ddim)</sup>. Expand

Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces

- Computer Science
- TAMC
- 2007

It is proved that for every l > 0, each k-NNG in a metric space with doubling dimension γ has a vertex separator of size O(kl(32l + 8) log L S log n + n l ), where L and S are respectively the maximum and minimum distances between any two points in P . Expand

The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension

- Mathematics, Computer Science
- Efficient Algorithms
- 2009

It is proved that, if the doubling dimension of S is a constant, any directed graph satisfying the weak gap property has O(n) edges and total weight $O(log n) \cdot wt({\mathord{\it MST}}(S)$, where wt denotes the weight of a minimum spanning tree of S. Expand

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

- Computer Science, Mathematics
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- 2020

The paper designs the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth) and shows the two following structural results for minor-free metrics. Expand

A Simple Proof of the Existence of a Planar Separator

- Mathematics, Computer Science
- ArXiv
- 2011

A simple proof of the existence of a planar separator is provided by showing that it is an easy consequence of the circle packing theorem and reprove other results on separators. Expand