Bisecting two subsets in 3-connected graphs
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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].
- Convex embeddings and bisections of 3-connected graphs
- A robust algorithm for bisecting a triconnected graph with two resource sets
- scientific article; zbMATH DE number 4093513 (Why is no real title available?)
- Convex Partitions with 2-Edge Connected Dual Graphs
- Algorithms and Computation
- Bisecting a 4-connected graph with three resource sets
This page was built for publication: Bisecting two subsets in 3-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511243)
