Planar Separator Theorem - Constructions - Simple Cycle Separators

Simple Cycle Separators

For a graph that is already maximal planar it is possible to show a stronger construction of a simple cycle separator, a cycle of small length such that the inside and the outside of the cycle (in the unique planar embedding of the graph) each have at most 2n/3 vertices. Miller (1986) proves this (with a separator size of √8√n) by using the Lipton–Tarjan technique for a modified version of breadth first search in which the levels of the search form simple cycles.

Alon, Seymour & Thomas (1994) prove the existence of simple cycle separators more directly: they let C be a cycle of at most √8√n vertices, with at most 2n/3 vertices outside C, that forms as even a partition of inside and outside as possible, and they show that these assumptions force C to be a separator. For otherwise, the distances within C must equal the distances in the disk enclosed by C (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally, C must have length exactly √8√n, as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in C are numbered (in clockwise order) from 1 to √8√n, and vertex i is matched up with vertex √8√n − i + 1, then these matched pairs can be connected by vertex-disjoint paths within the disk, by a form of Menger's theorem for planar graphs. However, the total length of these paths would necessarily exceed n, a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most (3/√2)√n, approximately 2.12√n.

Djidjev & Venkatesan (1997) further improved the constant factor in the simple cycle separator theorem to 1.97√n. Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most 2√n, and can generate separators with smaller size at the expense of a more uneven partition of the graph. In 2-connected planar graphs that are not maximal, there exist simple cycle separators with size proportional to the Euclidean norm of the vector of face lengths that can be found in near-linear time.