Bisecting Two Subsets in 3-Connected Graphs
Hiroshi Nagamochi6 
, Yoshitaka Nakao6, Toshihide Ibaraki6 and Tibor Jordán7
| (6) |
Kyoto University, Kyoto Japan, 606-8501 |
| (7) |
BRICS, University of Aarhus, 8000 Aarhus C, Denmark |
Abstract
Given two subsets T
1 and T
2 of vertices in a 3-connected graph G = (V,E), where |T
1| and |T
2| are even numbers, we show that V can be partitioned into two sets V
1 and V
2 such that the graphs induced by V
1 and V
2 are both connected and |V
1∩T
j| = |V
2∩T
j| = |T
j|/2 holds for each j = 1, 2. Such a partition can be found in O(|V|2) time. Our proof relies on geometric arguments. We define a new type of ‘convex embedding’ of k-connected graphs into real space R
k-1 and prove that for k = 3 such embedding always exists.
This research was partially supported by the Scientic Grant-in-Aid from Ministry of Education, Science, Sports and Culture
of Japan, and the subsidy from the In- amori Foundation. Part of this work was done while the second author visited the Department
of Applied Mathematics and Physics at Kyoto University, supported by the Monbusho International Scientic Research Program
no. 09044160.
References secured to subscribers.