Separators for intersection graphs of spheres

Jacob Fox, Jonathan Tidor · 2026

Read Separators for intersection graphs of spheres by Jacob Fox, Jonathan Tidor (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22204.txt.

Introduction

Fox and Tidor prove that intersection graphs of spheres admit optimal separators. A separator is a small vertex set whose removal splits the graph in a balanced way. For n spheres in d dimensions with m edges, they bound the separator size by a term in m and n. They show the bound is best possible for the given parameters. The same result holds for fat convex bodies and their boundaries in place of spheres.

Catalog record

CREATORJacob Fox, Jonathan Tidor
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49618
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22204

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Separators for intersection graphs of spheres Thanks: Fox was supported by NSF Awards DMS-2452737 and DMS-2154129. Tidor was supported in part by a Stanford Science Fellowship. This material is based in part upon work supported by the National Science Foundation under Grant No. DMS-1928930, while the authors were in residence at the Simons Laufer Mathematical Sciences Institute in Berkeley, California, during the Spring 2025 semester. Jacob Fox, Jonathan Tidor Abstract . We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension d d . One of our results is that if an intersection graph of n n spheres in ℝ d \mathbb{R}^{d} has m m edges, then it contains a balanced separator of size O d ​ ( m 1 / d ​ n 1 − 2 / d ) 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. 1. Introduction For a graph G=(V,E) , a balanced separator is a vertex set \mathcal{X}\subseteq V such that each connected component of G\setminus\mathcal{X} contains at most \tfrac{2}{3}|V| vertices. In 1979, Lipton and Tarjan [ 15 ] showed that n -vertex planar graphs have balanced separators of size O(\sqrt{n}) . There are many different characterizations of planar graphs that each lead to a different extension of the Lipton–Tarjan separator theorem. For example, Wagner’s theorem [ 23 ] states that a graph is planar if and only if it does not contain K_{5} or K_{3,3} as a minor. The family of graphs that can be embedded in a fixed surface has a finite list of forbidden minors by the Robertson–Seymour theorem [ 19 ] . Gilbert, Hutchinson, and Tarjan [ 9 ] proved that every n -vertex graph which can be embedded in a surface of genus g has a separator of size O(\sqrt{gn}) . Later, Alon, Seymour, and Thomas [ 1 ] proved that for every graph H , every n -vertex graph that does not contain H as a minor has a separator of size at most O_{H}(\sqrt{n}) . Another important characterization of planar graphs is the Koebe–Andreev–Thurston circle packing theorem, which says that a graph is planar if and only if it is the intersection graph of interior-disjoint disks in the plane. (This means that there is a collection of interior-disjoint disks, one corresponding to each vertex, so that two vertices are connected by an edge if and only if the corresponding disks are tangent.) This leads to another way to try to extend the Lipton–Tarjan separator theorem, to intersection graphs of geometric objects. A string graph is an intersection graph of arcwise-connected sets in the plane, so planar graphs are string graphs. The Lipton–Tarjan separator theorem has been extended in several works studying separators for string graphs [ 6 , 7 , 12 , 13 , 17 ] , and we now know that every string graph with m edges has a balanced separator of size O(\sqrt{m}) . Graphs with a small balanced separator are poor expanders, and one can utilize the separator for many applications, including in fast divide-and-conquer type algorithms for many algorithmically hard graph problems (see, for example, [ 16 ] ), extremal applications (see, for example, [ 8 , 14 ] ), and enumerative problems (see, for example, [ 5 ] ). In this paper, we are interested in finding small separators for intersection graphs of geometric objects in higher dimensions. Miller, Teng, Thurston, and Vavasis [ 18 ] proved a separator theorem for the intersection graph of balls in \mathbb{R}^{d} in which no point is in more than k of the balls. Generalizing this, we prove that every intersection graph of n balls in \mathbb{R}^{d} with m edges has 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. (Here and throughout the paper, we use the notation O_{d}(\cdot) to hide a multiplicative constant that depends only on the dimension d .) Proving a separator theorem for intersection graphs of spheres turns out to be more challenging as such graphs can have significantly more complicated combinatorial structure. Recently, Davies, Georgakopoulos, Hatzel, and McCarty [ 3 ] studied this problem under the constraint that the intersection graph is K_{t,t} -free, proving that if an intersection graph of n spheres in \mathbb{R}^{d} is K_{t,t} -free, then it has a balanced separator of size \tilde{O}_{d}(t^{10}n^{1-1/(2d+8)}) . We first study the problem in general. Despite their more complicated structure, we show that intersection graphs of spheres have the same size separators as intersection graphs of balls. Theorem 1.1 . An intersection graph of n spheres in \mathbb{R}^{d} with m edges has a balanced separator of size O_{d}(m^{1/d}n^{1-2/d}) . As a corollary, we show that every K_{t,t} -free intersection graph of n spheres has a separator of size O_{d}(t^{1/d}n^{1-1/d}) (see Corollary 3.9 ). This verifies a strengthening of a conjecture of Davies, Georgakopoulos, Hatzel and McCarty [ 3 , Conjecture 20] . Both Theorem 1.1 and the corollary are best possible up to the constant factor depending on the dimension d (see Proposition 4.1 ). We also prove a refinement of Theorem 1.1 which gives a separator whose size depends on the degree sequence of the intersection graph. As a corollary, we prove that every K_{t,t} -free intersection graph of spheres in \mathbb{R}^{d} has average degree O_{d}(t) . It follows that K_{t,t} -free intersection graphs of spheres in \mathbb{R}^{d} have chromatic number O_{d}(t) . We further study intersection graphs of other geometric objects in Section 4 . We generalize our results from balls and spheres to fat convex bodies and their boundaries. Unlike the planar case, we show that both the fatness and convexity assumptions are necessary in dimensions three and larger: no non-trivial separator exists for the intersection graph of general convex bodies or general fat bodies. Finally, as separators have many algorithmic applications, in Section 5 we show that there are efficient randomized algorithms for finding such separators of intersection graphs of balls or spheres. 2. Separators for intersection graphs of balls Let \mathcal{B} be a collection of balls in \mathbb{R}^{d} . The intersection graph of \mathcal{B} , denoted G(\mathcal{B}) , is the graph with vertex set \mathcal{B} where two balls are adjacent if they intersect. The collection \mathcal{B} is k -ply if every point of \mathbb{R}^{d} is contained in at most k balls. Miller, Teng, Thurston, and Vavasis [ 18 ] proved the following separator theorem for intersection graphs of balls. Theorem 2.1 ( [ 18 ] ) . Let \mathcal{B} be a k -ply collection of n balls in \mathbb{R}^{d} . Then G(\mathcal{B}) has a balanced separator of size O_{d}(k^{1/d}n^{1-1/d}) . A more recent proof of this result was given by Har-Peled [ 10 ] . Using his techniques, we are able to give a more refined version of the Miller–Teng–Thurston–Vavasis separator theorem. (Similar techniques also appeared in an earlier work of Smith and Wormald [ 20 ] .) Given a collection of balls \mathcal{B} , for each point x\in\mathcal{B} , the ply of x , denoted p(x) , is the number of balls in \mathcal{B} which contain

Read the complete text