### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 18 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2002 |

### Publication series

Name | Memorandum Faculteit TW |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1632 |

ISSN (Print) | 0169-2690 |

### Keywords

- EWI-3452
- MSC-05C12
- MSC-05C15
- IR-65819
- METIS-208266

### Cite this

*Stars and bunches in planar graphs. Part I: Triangulations*. (Memorandum Faculteit TW; No. 1632). Enschede: University of Twente, Department of Applied Mathematics.

}

*Stars and bunches in planar graphs. Part I: Triangulations*. Memorandum Faculteit TW, no. 1632, University of Twente, Department of Applied Mathematics, Enschede.

**Stars and bunches in planar graphs. Part I: Triangulations.** / Borodin, O.V.; Broersma, Haitze J.; Glebov, A.; van den Heuvel, J.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Stars and bunches in planar graphs. Part I: Triangulations

AU - Borodin, O.V.

AU - Broersma, Haitze J.

AU - Glebov, A.

AU - van den Heuvel, J.

N1 - Imported from MEMORANDA

PY - 2002

Y1 - 2002

N2 - Given a plane graph, a $k$-star at $u$ is a set of $k$ vertices with a common neighbour $u$; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have the same end vertices and the edges of the paths form consecutive edges (\,in the natural order in the plane graph\,) around the two end vertices. We prove a theorem on the structure of plane triangulations in terms of stars and bunches. The result states that a plane triangulation contains a $(d-1)$-star centred at a vertex of degree $d\leq5$ and the sum of the degrees of the vertices in the star is bounded, or there exists a large bunch.

AB - Given a plane graph, a $k$-star at $u$ is a set of $k$ vertices with a common neighbour $u$; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have the same end vertices and the edges of the paths form consecutive edges (\,in the natural order in the plane graph\,) around the two end vertices. We prove a theorem on the structure of plane triangulations in terms of stars and bunches. The result states that a plane triangulation contains a $(d-1)$-star centred at a vertex of degree $d\leq5$ and the sum of the degrees of the vertices in the star is bounded, or there exists a large bunch.

KW - EWI-3452

KW - MSC-05C12

KW - MSC-05C15

KW - IR-65819

KW - METIS-208266

M3 - Report

SN - 0169-2690

T3 - Memorandum Faculteit TW

BT - Stars and bunches in planar graphs. Part I: Triangulations

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -