|
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
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>>
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, 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 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.
|
|