The Planar Separator Theorem states that any planar graph $G=(V,E)$ with $n$ nodes has a separator $S\subset V$ of size $O(\sqrt{n})$, that is, a subset $S$ such that removing $S$ from $V$ splits the graph into components of size at most $2n/3$. The Planar Separator Theorem has proven useful in developing efficient algorithms for various problems on planar graphs. Unfortunately, intersection graphs of geometric objects typically do not admit a separator of small size. Indeed, even a unit-disk graph does not necessarily have a small separator, because it can have arbitrarily large cliques. However, many geometric intersection graphs (including disk graphs) do admit so-called clique-based separators: separators that consist of a small number of cliques, instead of a small number of nodes. In this talk I will survey recent work on constructing clique-based separators, and I will discuss some applications.
