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 ⋳ V and five natural numbers n_1, n_2, n_3, n_4, n_5 such that Σ^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 ⋳ V_i, ∣V_i∣ = n_i and V_i induces a connected subgraph of G for each i, 1 ≤ I ≤ 5. 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_1, u_2, u_3, u_4, u_5 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.
社団法人電子情報通信学会の論文
2001-09-01