A plane graph representation of triconnected graphs

Given a graph G = (V, E), a set S = {s(1), s(2), ..., s(k)} of k vertices of V. and k natural numbers n(1), n(2), ..., n(k) such that Sigma(k)(i=1) n(i) = vertical bar V vertical bar, the k-partition problem is to find a partition V-1, V-2, ..., V-k of the vertex set V such that vertical bar V-i vertical bar = n(i), s(i), is an element of V-i, and V-i induces a connected subgraph of G for each i = 1,2, ..., k. For the tripartition problem on a triconnected graph, a naive algorithm can be designed based on a directional embedding of G in the two-dimensional Euclidean space. However, for graphs of large number of vertices, the implementing of this algorithm requires high precision real arithmetic to distinguish two close vertices in the plane. In this paper, we propose an algorithm for dealing with the tripartition problem by introducing a new data structure called the region graph, which represents a kind of combinatorial embedding of the given graph in the plane. The algorithm constructs a desired tripartition combinatorially in the sense that it does not require any geometrical computation with actual coordinates in the Euclidean space. (C) 2010 Elsevier B.V. All rights reserved.