Bisecting two subsets in 3-connected graphs (Q4511243)

The \(k\)-bisection problem is defined as follows: Given a graph \(G = (V,E)\) and sets \(T_1, T_2, \dots, T_k\) included in \(V\) with \(|T_1|, |T_2|, \dots, |T_k|\) even numbers. Find a bipartition of \(V\) into two sets \(V_1, V_2\) such that the graph \(G[V_i]\) induced by each \(V_i\) is connected and \(|V_1 \cap T_j|= |V_2 \cap T_j|\) \((= |T_j|/2)\) holds for \(j = 1, \dots, k\). The authors consider the \(2\)-bisection problem and show that for each \(3\)-connected graph a \(2\)-bisection exists and can be constructed by a \(O(n^2)\) algorithm. For proving this result it is shown that every \(3\)-connected graph \(G\) has a strictly convex embedding, i.e., it can be embedded in the plane such that the convex hull of the vertices corresponds to a cycle \(C\) of \(G\) and that each vertex in \(V \setminus V(C)\) is in the convex hull of its neighbors. This implies that each straight line in the plane separates \(G\) into two connected subgraphs. Thus, using the linear time `ham-sandwich cut' algorithm by \textit{C.-Y. Lo, J. Matoušek} and \textit{W. Steiger} [Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, No. 4, 433-452 (1994; Zbl 0806.68061)], \(T_1\) and \(T_2\) can be bisected simultaneously. It is shown that an strictly convex embedding for a \(3\)-connected graph can be found in \(O(n^2)\). Furthermore it is stated without proof that deciding whether an arbitrary graph has an strictly convex embedding is NP-hard. For the more general case of the \(k\)-bisection problem, the following conjecture is given. If \(G\) is a \((k+1)\)-connected graph and \(T_1, T_2, \dots, T_k\) are pairwise disjoint vertex sets of \(G\), each with an even number of vertices, then \(G\) has a \(k\)-bisection. For the entire collection see [Zbl 0933.00045].