Planar Separator Theorem - Other Classes of Graphs

Other Classes of Graphs

Some sparse graphs do not have separators of sublinear size: in an expander graph, deleting up to a constant fraction of the vertices still leaves only one connected component.

Possibly the earliest known separator theorem is a result of Jordan (1869) that any tree can be partitioned into subtrees of at most 2n/3 vertices each by the removal of a single vertex. In particular, the vertex that minimizes the maximum component size has this property, for if it did not then its neighbor in the unique large subtree would form an even better partition. By applying the same technique to a tree decomposition of an arbitrary graph, it is possible to show that any graph has a separator of size at most equal to its treewidth.

If a graph G is not planar, but can be embedded on a surface of genus g, then it has a separator with O((gn)1/2) vertices. Gilbert, Hutchinson & Tarjan (1984) prove this by using a similar approach to that of Lipton & Tarjan (1979). They group the vertices of the graph into breadth-first levels and find two levels the removal of which leaves at most one large component consisting of a small number of levels. This remaining component can be made planar by removing a number of breadth-first paths proportional to the genus, after which the Lipton–Tarjan method can be applied to the remaining planar graph. The result follows from a careful balancing of the size of the removed two levels against the number of levels between them. If the graph embedding is given as part of the input, its separator can be found in linear time. Graphs of genus g also have edge separators of size O((gΔn)1/2).

Graphs of bounded genus form an example of a family of graphs closed under the operation of taking minors, and separator theorems also apply to arbitrary minor-closed graph families. In particular, if a graph family has a forbidden minor with h vertices, then it has a separator with O(h√n) vertices, and such a separator can be found in time O(n1 + ε) for any ε > 0.

The circle separator method of Miller et al. (1997) generalizes to the intersection graphs of any system of d-dimensional balls with the property that any point in space is covered by at most some constant number k of balls, to k-nearest-neighbor graphs in d dimensions, and to the graphs arising from finite element meshes. The sphere separators constructed in this way partition the input graph into subgraphs of at most n(d + 1)/(d + 2) vertices. The size of the separators for k-ply ball intersection graphs and for k-nearest-neighbor graphs is O(k1/dn1 − 1/d).