Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-014 (November 20, 2008)

A Plane Graph Representation of Triconnected Graphs
by Shunsuke Ota, Ehab Morsy, and Hiroshi Nagamochi

pdf File

Given a graph $G=(V,E)$, a set $S=\{s_1,s_2,\dots , s_k\}$ of $k$ vertices of $V$, and $k$ natural numbers $n_1,n_2,\dots ,n_k$ such that $\sum _{i=1}^k n_i = |V|$, the $k$-partition problem is to find a partition $V_1,V_2,\dots ,V_k$ of the vertex set $V$ such that $|V_i|=n_i$, $s_i\in V_i$, and $V_i$ induces a connected subgraph of $G$ for each $i=1,2,\ldots,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, implementing of this algorithm requires high precision real arithmetic to distinguish two close vertices in the plane. In this paper, we propose an algorithm to the tripartition problem by introducing a new data structure called {\em region graph}, which represents some 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.