G, which is a generalization of an st-numbering and a "canonical ordering" known in the area of graph drawings." />

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

Sayaka NAGAI  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.9   pp.2330-2337
Publication Date: 2001/09/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
graph,  algorithm,  partition,  

Full Text: PDF>>
Buy this Article



Summary: 
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.