Georgia Institute of Technology College of Sciences

We discuss the sphere dimension of a graph. This is the smallest integer $d$ such that the graph can be represented as the intersection graph of a collection of spheres in $\mathbb{R}^d$. We show that graphs with small sphere dimension have small balanced separators, as long as they exclude a complete bipartite graph $K_{t,t}$. This property is connected to forbidding shallow minors and can be used to develop divide-and-conquer algorithms. This is joint work with James Davies, Agelos Georgakopoulos, and Meike Hatzel.