For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs
Sayaka NAGAI Shin-ichi NAKANO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/09/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
graph, algorithm, partition,
Full Text: PDF>>
Given a graph G=(V,E), five distinct vertices u1,u2,u3,u4,u5 V and five natural numbers n1,n2,n3,n4,n5 such that Σ5i=1ni=|V|, we wish to find a partition V1,V2,V3,V4,V5 of the vertex set V such that ui Vi, |Vi|=ni and Vi 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 u1,u2,u3,u4,u5 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.