Finding small simple cycle separators for 2-connected planar graphs.
Gary Lee Miller · 1984
We show that every 2-connected triangulated planar graph with n vertices has a simple cycle C of length at most [email protected]@@@n which separates the interior vertices A from the exterior vertices B such that neither A nor B contains more than 2/3n vertices. The method also gives a linear time algorithm for finding the simple cycle. In general, if the maximum face size is d then we exhibit a cycle C as above of size at most [email protected]@@@2d•n.