Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs

Abstract

In this paper, we consider the class ${\mathcal{C}}^d$ of sphere intersection graphs in ${\mathbb{R}}^d$ for $d\ge 2$. We show that for each integer $t$, the class of all graphs in ${\mathcal{C}}^d$ that exclude $K_{t,t}$ as a subgraph has strongly sublinear separators. We also prove that ${\mathcal{C}}^d$ has asymptotic dimension at most $2d+2$.

20 pages, 2 figures