Planar Separator Theorem - Statement of The Theorem

Statement of The Theorem

As it is usually stated, the separator theorem states that, in any n-vertex planar graph G = (V,E), there exists a partition of the vertices of G into three sets A, S, and B, such that each of A and B has at most 2n/3 vertices, S has O(√n) vertices, and there are no edges with one endpoint in A and one endpoint in B. It is not required that A or B form connected subgraphs of G. S is called the separator for this partition.

An equivalent formulation is that the edges of any n-vertex planar graph G may be subdivided into two edge-disjoint subgraphs G₁ and G₂ in such a way that both subgraphs have at least n/3 vertices and such that the intersection of the vertex sets of the two subgraphs has O(√n) vertices in it. Such a partition is known as a separation. If a separation is given, then the intersection of the vertex sets forms a separator, and the vertices that belong to one subgraph but not the other form the separated subsets of at most 2n/3 vertices. In the other direction, if one is given a partition into three sets A, S, and B that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in A belong to G₁, the edges with an endpoint in B belong to G₂, and the remaining edges (with both endpoints in S) are partitioned arbitrarily.

The constant 2/3 in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval (1/2,1) without changing the form of the theorem: a partition into more equal subsets may be obtained from a less-even partition by repeatedly splitting the larger sets in the uneven partition and regrouping the resulting connected components.