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

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