A Linear-Time Algorithm for Four-Partitioning Four-Connected Planar Graphs

Nakano, Shin-Ichi and Rahman, Md. Saidur and Nishizeki, Takao (1997) A Linear-Time Algorithm for Four-Partitioning Four-Connected Planar Graphs. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 334-344(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_58).

Full text not available from this repository.


Given a graph G=(V,E), four distinct vertices u_1, u_2, u_3, u_4 \in V and four natural numbers n_1, n_2, n_3, n_4 such that \sum_{i=1}^4 n_i=|V|, we wish to find a partition V_1, V_2, V_3, V_4 of the vertex set V such that u_i \in V_i, |V_i|=n_i and V_i induces a conneceted subgraph of G for each 1 \le i \le 4. In this paper we give a simple linear-time algorithm to find such a partition if G is a 4-connected planar graph and u_1, u_2, u_3, u_4 are located on the same face of a plane embedding of G. Our algorithm is based on a "4-canonical decomposition" of G, wich is generalization of an st-numbering and a "canonical 4-ordering" known in the area of graph drawings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_58
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/195

Actions (login required)

View Item View Item