A robust algorithm for bisecting a triconnected graph with two resource sets

Given two disjoint subsets T1 and T2 of nodes in a 3-connected graph G=(V,E) with a node set V and an arc set E, where |T1| and |T2| are even numbers, it is known that V can be partitioned into two sets V1 and V2 such that the graphs induced by V1 and V2 are both connected and |V1∩Tj|=|V2∩Tj|=|Tj|/2 holds for each j=1,2. An O(|V|2log|V|) time and O(|V|+|E|) space algorithm for finding such a bipartition has been proposed based on a geometric argument, where G is embedded in the plane R2 and the node set is bipartitioned by a ham-sandwich cut on the embedding. A naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on R2. In this paper, we propose an O(|V|2) time and space algorithm to the problem. The new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in R2 and thereby no longer needs to store any real number for embedded points. Although the new algorithm seems to need more space complexity, it can be implemented only with |V| linked lists such that each element stores an integer in [1,|V|].