Given two disjoint subsets T-1 and T-2 of nodes in a 3-connected graph G = (V, E) with a node set V and an arc set E, where vertical bar T(1)vertical bar and vertical bar T(2)vertical bar are even numbers, it is known 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 vertical bar v(1) boolean AND T(j)vertical bar = vertical bar V-2 boolean AND T(j)vertical bar = T(j)vertical bar/2 holds for each j = 1,2. Ano(vertical bar V vertical bar(2) log vertical bar V vertical bar) time and O(vertical bar V vertical bar + vertical bar E vertical bar) space algorithm for finding such a bipartition has been proposed based on a geometric argument, where G is embedded in the plane R-2 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 R-2. In this paper, we propose an O(vertical bar V vertical bar(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 R-2 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 vertical bar V vertical bar linked lists such that each element stores an integer in [1, vertical bar V vertical bar]. (c) 2005 Elsevier B.V. All rights reserved.