2504.00932

#1 Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs [PDF] [Copy] [Kimi] [REL]

Authors: James Davies, Agelos Georgakopoulos, Meike Hatzel, Rose McCarty

In this paper, we consider the class $\mathcal{C}^d$ of sphere intersection graphs in $\mathbb{R}^d$ for $d \geq 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$.

Subjects: Combinatorics , Computational Geometry , Discrete Mathematics , Metric Geometry

Publish: 2025-04-01 16:05:36 UTC

---