A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs

Sayaka NAGAI, Shin-ichi NAKANO

Summary :

Given a graph G=(V,E), five distinct vertices u₁,u₂,u₃,u₄,u₅ V and five natural numbers n₁,n₂,n₃,n₄,n₅ such that Σ⁵_i=1n_i=|V|, we wish to find a partition V₁,V₂,V₃,V₄,V₅ of the vertex set V such that u_i V_i, |V_i|=n_i and V_i induces a connected subgraph of G for each i, 1i5. In this paper we give a simple linear-time algorithm to find such a partition if G is a 5-connected internally triangulated plane graph and u₁,u₂,u₃,u₄,u₅ are located on the outer face of G. Our algorithm is based on a "5-canonical decomposition" of G, which is a generalization of an st-numbering and a "canonical ordering" known in the area of graph drawings.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.9 pp.2330-2337
• Publication Date: 2001/09/01
• Type of Manuscript: PAPER
• Category: Algorithms and Data Structures

Authors

Sayaka NAGAI
Shin-ichi NAKANO

Keyword

graph,  algorithm,  partition