Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T10:49:42.808Z Has data issue: false hasContentIssue false

Combinatorial Local Planarity and the Width of Graph Embeddings

Published online by Cambridge University Press:  20 November 2018

Bojan Mohar*
Affiliation:
Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia, bojan.mohar@uni-lj.ac.mail.yu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a graph embedded in a closed surface. The embedding is “locally planar” if for each face, a “large” neighbourhood of this face is simply connected. This notion is formalized, following [RV], by introducing the width ρ(ψ) of the embedding ψ. It is shown that embeddings with ρ(ψ) ≥ 3 behave very much like the embeddings of planar graphs in the 2-sphere. Another notion, “combinatorial local planarity”, is introduced. The criterion is independent of embeddings of the graph, but it guarantees that a given cycle in a graph G must be contractible in any minimal genus embedding of G (either orientable, or non-orientable). It generalizes the width introduced before. As application, short proofs of some important recently discovered results about embeddings of graphs are given and generalized or improved. Uniqueness and switching equivalence of graphs embedded in a fixed surface are also considered.

Keywords

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1992