Densely embedded graphs (Q908930)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Densely embedded graphs |
scientific article |
Statements
Densely embedded graphs (English)
0 references
1992
0 references
Let G be a graph embedded in a surface S. The face-width of the embedding is the minimum size \(| C\cap G|\) over all noncontractible cycles C in S. The face-width measures how densely a graph is embedded in a surface; equivalently, how well an embedded graph represents a surface. In this paper we present a construction of densely embedded graphs with a variety of interesting properties. The first application is the construction of embeddings where both the primal and the dual graph have large girth. A second application is the construction of a graph with embeddings on two different surfaces, each embedding of large face-width. These embeddings are counterexamples to a conjecture by Robertson and Vitray. In the third application we examine the number of triangles needed to triangulate a surface S such that every noncontractible cycle is of length at least k. Surprisingly, for large g the number is approximately 4g, regardless of k. The fourth application is the construction of trivalent polygonal graphs. We close with some observations and directions for further research.
0 references
graph embedding
0 references
maps
0 references
triangulations
0 references
face-width
0 references
densely embedded graphs
0 references