Planar Separator Theorem - Constructions - Edge Separators

A variation of the planar separator theorem involves edge separators, small sets of edges forming a cut between two subsets A and B of the vertices of the graph. The two sets A and B must each have size at most a constant fraction of the number n of vertices of the graph (conventionally, both sets have size at most 2n/3), and each vertex of the graph belongs to exactly one of A and B. The separator consists of the edges that have one endpoint in A and one endpoint in B. Bounds on the size of an edge separator involve the degree of the vertices as well as the number of vertices in the graph: the planar graphs in which one vertex has degree n − 1, including the wheel graphs and star graphs, have no edge separator with a sublinear number of edges, because any edge separator would have to include all the edges connecting the high degree vertex to the vertices on the other side of the cut. However, every planar graph with maximum degree Δ has an edge separator of size O(√(Δn)).

A simple cycle separator in the dual graph of a planar graph forms an edge separator in the original graph. Applying the simple cycle separator theorem of Gazit & Miller (1990) to the dual graph of a given planar graph strengthens the O(√(Δn)) bound for the size of an edge separator by showing that every planar graph has an edge separator whose size is proportional to the Euclidean norm of its vector of vertex degrees.

Papadimitriou & Sideri (1996) describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph G into two subgraphs of equal size, when G is an induced subgraph of a grid graph with no holes or with a constant number of holes. However, they conjecture that the problem is NP-complete for arbitrary planar graphs, and they show that the complexity of the problem is the same for grid graphs with arbitrarily many holes as it is for arbitrary planar graphs.