Convex embeddings and bisections of 3-connected graphs (Q1410408)

The authors prove the following result. Given a 3-connected graph \(G\) and two disjoints sets of vertices \(T_1\) and \(T_2\) of even size, it is possible to partion the vertex set of \(G\) into sets \(V_1\) and \(V_2\) such that: (1) the subgraphs induced by \(V_i\) (for \(i=1,2)\) are connected, and (2) \(|V_1 \cap T_i|=|V_2 \cap T_i|\) (for \(i=1,2)\). In fact, such a partition can be found in \(O(|V|^2 \log |V|)\) time. The proof is carried out in two steps; first it is proven that \(G\) has a convex embedding, then the well-known ham-sandwich theorem gives an appropriate cut. The later one can be done effectively, see \textit{H. Edelsbrunner} and \textit{R. Waupotitsch} [J. Symb. Comput. 2, 171-178 (1986; Zbl 0623.68058)].