A LinearTime Algorithm for FourPartitioning FourConnected Planar GraphsNakano, ShinIchi and Rahman, Md. Saidur and Nishizeki, Takao (1997) A LinearTime Algorithm for FourPartitioning FourConnected Planar Graphs. In: Symposium on Graph Drawing, GD '96, September 1820, 1996 , pp. 334344(Official URL: http://dx.doi.org/10.1007/3540624953_58). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540624953_58
AbstractGiven 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 lineartime algorithm to find such a partition if G is a 4connected 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 "4canonical decomposition" of G, wich is generalization of an stnumbering and a "canonical 4ordering" known in the area of graph drawings.
Actions (login required)
