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.
Read more about this topic: Planar Separator Theorem, Constructions
Famous quotes containing the words simple and/or cycle:
“It is very difficult for people to believe the simple fact that every persecutor was once a victim. Yet it should be very obvious that someone who was allowed to feel free and strong from childhood does not have the need to humiliate another person.”
—Alice Miller (20th century)
“The lifelong process of caregiving, is the ultimate link between caregivers of all ages. You and I are not just in a phase we will outgrow. This is life—birth, death, and everything in between.... The care continuum is the cycle of life turning full circle in each of our lives. And what we learn when we spoon-feed our babies will echo in our ears as we feed our parents. The point is not to be done. The point is to be ready to do again.”
—Paula C. Lowe (20th century)