A linear-time algorithm for five-partitioning five-connected internally triangulated plane graphs

Given a graph G = (V, E), five distinct vertices u(1),u(2),u(3),u(4),u(5) i s an element of V and five natural numbers n(1), n(2), n(3), n(4), n(5), su ch that Sigma (5)(i=1) n(i) = \V \, we wish to find a partition V-1,V-2,V-3 ,V-4,V-5 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 eq ual to i less than or equal to 5. In this paper we give a simple linear-tim e algorithm to find such a partition if G is a 5-connected internally trian gulated plane graph and u(1), u(2), u(3), u(4), us are located on the outer face of G. Our algorithm is based on a "5-canonical decomposition" of G, w hich is a generalization of an st-numbering and a "canonical ordering" know n in the area of graph drawings.