The search functionality is under construction.

The search functionality is under construction.

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*, 1*i**G* is a 5-connected 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 "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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Sayaka NAGAI, Shin-ichi NAKANO, "A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 9, pp. 2330-2337, September 2001, doi: .

Abstract: 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*, 1*i**G* is a 5-connected 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 "5-canonical decomposition" of *G*, which is a generalization of an *st*-numbering and a "canonical ordering" known in the area of graph drawings.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_9_2330/_p

Copy

@ARTICLE{e84-a_9_2330,

author={Sayaka NAGAI, Shin-ichi NAKANO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs},

year={2001},

volume={E84-A},

number={9},

pages={2330-2337},

abstract={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*, 1*i**G* is a 5-connected 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 "5-canonical decomposition" of *G*, which is a generalization of an *st*-numbering and a "canonical ordering" known in the area of graph drawings.

keywords={},

doi={},

ISSN={},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2330

EP - 2337

AU - Sayaka NAGAI

AU - Shin-ichi NAKANO

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2001

AB - 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*, 1*i**G* is a 5-connected 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 "5-canonical decomposition" of *G*, which is a generalization of an *st*-numbering and a "canonical ordering" known in the area of graph drawings.

ER -