Stars and bunches in planar graphs. Part I: Triangulations
Borodin, O.V. and Broersma, H.J. and Glebov, A. and Heuvel, J. van den (2002) Stars and bunches in planar graphs. Part I: Triangulations. [Report]

PDF
359kB 
Abstract:  Given a plane graph, a star at is a set of vertices with a common neighbour ; 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 star centred at a vertex of degree and the sum of the degrees of the vertices in the star is bounded, or there exists a large bunch.

Item Type:  Report 
Additional information:  Imported from MEMORANDA 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65819 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 208266