Stars and bunches in planar graphs. Part I: Triangulations

O.V. Borodin, H.J. Broersma, A. Glebov, J. van den Heuvel

Research output: Book/ReportReportProfessional

79 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages18
Publication statusPublished - 2002

Publication series

NameMemorandum
PublisherUniversity of Twente, Department of Applied Mathematics
No.1632
ISSN (Print)0169-2690

Keywords

  • MSC-05C12
  • MSC-05C15

Fingerprint

Dive into the research topics of 'Stars and bunches in planar graphs. Part I: Triangulations'. Together they form a unique fingerprint.

Cite this