page_title: Planar separator theorem
section_title: Other classes of graphs
hierarchical_section_title: Planar separator theorem / Other classes of graphs
context_page_description: In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(√n) vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
  A weaker form of the separator theorem with O(√n log n) vertices in the separator instead of O(√n) was originally proven by Ungar, and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan. Since their work, the separator theorem has been reproven in several different ways, the constant in the O(√n) term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.
  Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph.
context_section_description: 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 n/2 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/ᵈn1 - 1/ᵈ).
caption: An intersection graph of disks, with at most k = 5 disks covering any point of the plane