The search functionality is under construction.
The search functionality is under construction.

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

Sayaka NAGAI, Shin-ichi NAKANO

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.9 pp.2330-2337
Publication Date
2001/09/01
Publicized
Online ISSN
DOI
Type of Manuscript
PAPER
Category
Algorithms and Data Structures

Authors

Keyword