A LINEAR-TIME ALGORITHM FOR 4-PARTITIONING 4-CONNECTED PLANAR GRAPHS

Given a graph G = (V,E), four distinct vertices u(1),u(2),u(3),u(4) is an element of V and four natural numbers n(1),n(2),n(3),n(4) such tha t Sigma(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) is an element of V-i, \V-i\ = n(i) and V-i induces a connected subgraph of G for each i, 1 less than or equal to i less than or equal to 4. In this paper we give a simple lin ear-time algorithm to find such a partition if G is a 4-connected plan ar graph and u(1), u(2), u(3) and u(4) are located on the same face of a plane embedding of G. Our algorithm is based on a ''4-canonical dec omposition'' of G, which is a generalization of an st-numbering and a ''canonical 4-ordering'' known in the area of graph drawings. (C) 1997 Elsevier Science B.V.