Reduced constants for simple cycle graph separation (Q1920221)

If \(G\) is an \(n\) vertex maximal planar graph and \(\delta\leq 1/3\), then the vertex set of \(G\) can be partitioned into three sets \(A\), \(B\), \(C\) such that neither \(A\) nor \(B\) contains more than \((1- \delta)n\) vertices, no edge from \(G\) connects a vertex in \(A\) to a vertex in \(B\), and \(C\) is a cycle in \(G\) containing no more than \((\sqrt {2\delta}+ \sqrt {2-2\delta}) \sqrt {n}+ O(1)\) vertices. Specifically, when \(\delta= 1/3\), the separator \(C\) is of size \((\sqrt {2/3}+ \sqrt {4/3}) \sqrt {n}+ O(11)\), which is roughly \(1.97 \sqrt {n}\). The constant 1.97 is an improvement over the best known so far result of Miller \(2\sqrt {2} \approx 2.82\). If non-negative weights adding to at most 1 are associated with the vertices of \(G\), then the vertex set of \(G\) can be partitioned into three sets \(A\), \(B\), \(C\) such that neither \(A\) nor \(B\) has weight exceeding \(1- \delta\), no edge from \(G\) connects a vertex in \(A\) to a vertex in \(B\), and \(C\) is a simple cycle with no more then \(2\sqrt {n}+ O(1)\) vertices.