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, Berkeley, California, , pp. 334-344 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_58).

Full text not available from this repository.

Abstract

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
ID Code:195

Repository Staff Only: item control page

References

M.E. Dyer and A.M. Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10 (1985) 139-153.

S. Even. Graph Algorithms. Computer Science Press, Potomac (1979).

E. Györi. On division of connected subgraphs. Proc. 5th Hungarian Combinatorial Coll., (1978) 485-494.

E. Györi. Private communication. March 21, 1996.

L. Jou, H. Suzuki and T. Nishizeki. A linear algorithm for finding a nonseparating ear decomposition of triconnected planar graphds. Tech. Rep. of Information Proccessing Society of Japan. AL40-3 (1994).

G. Kant. A more compact visibility representation. Proc. of the 19th International Workshop on Graph Theoretic Concepts in Computer Science (WG '93), LNCS 790 (1994) 411-424.

G. Kant and X. He. Two algorithms for finding rectangular duals of planar graphs. proc. of the 19th International Workshop on Graph Theoretic Concepts in Computer Science (WG '93), LNCS 790 (1994) 396-410.

L. Lovász. A homology theory of for spanning trees of a graph. Acta Math. Acad. Sci. Hunger, 30 (1977) 241-251.

J. Ma and S.H. Ma. An O(k²n²) algorithm to find a k-patition in a k-connected graph. J. of Computer Sci. & Technol., 9, 1 (1994) 86-91.

H. Suzuki, N. Takahashi and T. Nishizeki. A linear algorithm for bipartition of biconnected graphs. Information Processing Letters 33, 5 (1990) 227-232.

H. Suzuki, N. Takahashi, T. Nishizeki, H. Miyano and S. Ueno. An algorithm for tripartitioning 3-connected graphs. Journal of Information Processing Society of Japan 31, 5 (1990) 584-592.

K. Wada and K. Kawaguchi. Efficient algorithms for triconnected graphs and 3-edge-connected graphs. Proc. of the 19th International Workshop on Graph Theoretic Concepts in Computer Science (WG '93), LNCS 790 (1994) 132-143.

K. Wada, A. Takaki, and K. Kawaguchi. Efficient algorithms for a mixed k-partition problem of graphs without specifying bases. Proc. of the 20th International Workshop on Graph Theoretic Concepts in Computer Science (WG '94), LNCS 903 (1995) 319-330.