Finding small simple cycle separators for 2-connected planar graphs (Q1085169)

A graph of order n is said to have a f(n)-vertex separator if there exists a partition of its vertices into three sets A, B and C such that \(| C| \leq f(n)\), \(| A|,| B| \leq 2n/3\) and no edge exists between A and B. \textit{R. J. Lipton} and \textit{R. E. Tarjan} [SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)] showed that planar graphs have \(\sqrt{8n}\)-vertex separators, and \textit{H. N. Djidjev} [C. R. Acad. Bulg. Sci. 35, 1053-1056 (1982; Zbl 0516.05051)] improved this to \(\sqrt{6n}.\) The author proves that for planar triangulations of order n there is always a \(\sqrt{8n}\)-vertex separator such that the set C is a simple cycle. The method also gives a linear time sequential algorithm for finding this simple cycle, and an NC parallel algorithm. In general, if the maximum face size in an embedded plane graph is d then a cycle C as above can be exhibited, being of size \(\leq 2\sqrt{nd}\).