Separators for intersection graphs of spheres
This provides foundational results for graph theory and computational geometry, with applications in algorithms and network analysis.
The paper proves the existence of optimal separators for intersection graphs of spheres and balls in any dimension, showing that such graphs contain balanced separators of size O_d(m^{1/d}n^{1-2/d}), which is best possible.
We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension $d$. One of our results is that if an intersection graph of $n$ spheres in $\mathbb{R}^d$ has $m$ edges, then it contains a balanced separator of size $O_d(m^{1/d}n^{1-2/d})$. This bound is best possible in terms of the parameters involved. The same result holds if the balls and spheres are replaced by fat convex bodies and their boundaries.