# Separators for sphere-packings and nearest neighbor graphs

@article{Miller1997SeparatorsFS, title={Separators for sphere-packings and nearest neighbor graphs}, author={Gary L. Miller and Shang-Hua Teng and William P. Thurston and Stephen A. Vavasis}, journal={J. ACM}, year={1997}, volume={44}, pages={1-29} }

A collection of <italic>n</italic> balls in <italic>d</italic> dimensions forms a <italic>k</italic>-ply system if no point in the space is covered by more than <italic>k</italic> balls. We show that for every <italic>k</italic>-ply system Γ, there is a sphere <italic>S</italic> that intersects at most <italic>O</italic>(<italic>k</italic><supscrpt>1/<italic>d</italic></supscrpt><italic>n</italic><supscrpt>1−1/<italic>d</italic></supscrpt>) balls of Γ and divides the remainder of Γ into two… Expand

#### 240 Citations

Coloring kk-free intersection graphs of geometric objects in the plane

- Computer Science, Mathematics
- SCG '08
- 2008

Using a mix of results on partially ordered sets and planar separators, the best known upper bound on the number of edges of a <i>k-quasi-planar topological graph</i> with </i>n vertices is improved and is shown to be correct. Expand

Constant factor approximation of vertex-cuts in planar graphs

- Mathematics, Computer Science
- STOC '03
- 2003

A structural theorem is proved for planar graphs, showing the existence of a near-optimal quotient vertex-cut whose high-level structure is that of a bounded-depth tree and an algorithm is developed that optimizes over such complex structures in running time that depends (exponentially) not on the size of the structure, but rather only on its depth. Expand

Computing the independence number of intersection graphs

- Computer Science, Mathematics
- SODA '11
- 2011

A subexponential time exact algorithm for computing the independence number of intersection graphs of arcwise connected sets in the plane, known to be an NP-hard task for general graphs. Expand

Tight bounds for the Min-Max boundary decomposition cost of weighted graphs

- Mathematics, Computer Science
- SPAA '06
- 2006

The upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Expand

A linear-time algorithm to find a separator in a graph excluding a minor

- Mathematics, Computer Science
- TALG
- 2009

A fast approximation algorithm for finding an independent set in a graph with no K-iℓ-minor and a trade-off between time complexity and the order of the separator is obtained. Expand

Balanced Line Separators of Unit Disk Graphs

- Mathematics, Computer Science
- WADS
- 2017

A geometric version of the graph separator theorem for the unit disk intersection graph is proved, and it is shown that no line-separator of sublinear size in $n$ exists when the authors look at disks of arbitrary radii. Expand

Balanced line separators of unit disk graphs

- Computer Science, Mathematics
- Comput. Geom.
- 2020

A geometric version of the graph separator theorem for the unit disk intersection graph is proved, and it is shown that no line-separator of sublinear size in n exists when the authors look at disks of arbitrary radii. Expand

Coloring Kk-free intersection graphs of geometric objects in the plane

- Computer Science, Mathematics
- Eur. J. Comb.
- 2012

It is proved that for any t and k, the chromatic number of every K"k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (c"tlognlogk)^c^l^o^g^k, where c is an absolute constant and c"t only depends on t. Expand

Geometric separator theorems and applications

- Mathematics, Computer Science
- Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
- 1998

A large number of "geometric separator theorems" are found, such as subexponential algorithms for traveling salesman tour and rectilinear Steiner minimal tree in R/sup d/, new point location algorithms, and new upper and lower bound proofs for "planar separatorTheorems". Expand

Clique-Based Separators for Geometric Intersection Graphs

- Computer Science
- ArXiv
- 2021

These results immediately imply sub-exponential algorithms for Maximum Independent Set, for Vertex Cover, for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes. Expand

#### References

SHOWING 1-10 OF 69 REFERENCES

Small sets supporting fary embeddings of planar graphs

- Mathematics, Computer Science
- STOC '88
- 1988

It is shown that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n, which settles a problem of Mohar. Expand

A deterministic linear time algorithm for geometric separators and its applications

- Computer Science, Mathematics
- SCG '93
- 1993

The deterministic algorithm hinges on the use of a new method forderiving the separator property of neighborhood systems and answers a majoralgorithmic open question posed by Miller, Teng, Thurston and Vavasis. Expand

Approximating center points with iterated radon points

- Computer Science, Mathematics
- SCG '93
- 1993

Ouralgorithm is a practical and provably good algorithm for approximating center points in any number of dimensions that has the potential to improve results in practice for constructing weak ε-nets and other geometricalgorithms. Expand

Shallow excluded minors and improved graph decompositions

- Mathematics, Computer Science
- SODA '94
- 1994

The notion of the limited-depth minor exclusion is introduced and it is proved that graphs that exclude small limited- depth minors have relatively small separators, which implies that any graph that excludes Kh as a minor has an O(hpn logn)-sized separator. Expand

A Separator Theorem for Graphs of Bounded Genus

- Mathematics, Computer Science
- J. Algorithms
- 1984

The main result of this paper is that if the authors can draw a graph on a surface of genus g, then they can bisect it by removing $O(\sqrt{gn})$ vertices, best possible to within a constant factor. Expand

Combinatorial aspects of geometric graphs

- Computer Science, Mathematics
- Comput. Geom.
- 1998

The main result implies that overlap graphs have “good” cut-covers, answering an open question of Kaklamanis, Krizanc and Rao (1993), and yields a combinatorial proof that overlap graph have separators of sublinear size. Expand

A separator theorem for graphs with an excluded minor and its applications

- Mathematics, Computer Science
- STOC '90
- 1990

It follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/ √ log n in polynomial time, find that size exactly and solve any sparse system of n linear equations in n unknowns in time O(n). Expand

Points, spheres, and separators: a unified geometric approach to graph partitioning

- Mathematics
- 1992

Geometry is full of visual imagination and concrete intuition. Such imagination and intuition is of great value not only for the research worker, but also for anyone who wishes to study and… Expand

Separators in two and three dimensions

- Mathematics, Computer Science
- STOC '90
- 1990

It is shown that every graph that is the 1-skeleton of a simplicial complex K in 3-dimensions has a separator of size O(c 2/3 + ~), which gets an O(n 2) time algorithm for solving linear systems that arise from the finite element method. Expand

The geometry of graphs and some of its algorithmic applications

- Computer Science, Mathematics
- Comb.
- 1995

Efficient algorithms for embedding graphs low-dimensionally with a small distortion, and a new deterministic polynomial-time algorithm that finds a (nearly tight) cut meeting this bound. Expand