
For FullText 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 LinearTime Algorithm for FivePartitioning FiveConnected Internally Triangulated Plane Graphs
Sayaka NAGAI Shinichi NAKANO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E84A
No.9
pp.23302337 Publication Date: 2001/09/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: graph, algorithm, partition,
Full Text: PDF(762.1KB)>>
Summary:
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, 1i5. In this paper we give a simple lineartime algorithm to find such a partition if G is a 5connected 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 "5canonical decomposition" of G, which is a generalization of an stnumbering and a "canonical ordering" known in the area of graph drawings.

