COMBINATORIAL LOCAL PLANARITY AND THE WIDTH OF GRAPH EMBEDDINGS

Let G be a graph embedded in a closed surface. The embedding is "locally planar" if for each face, a "large" neighbourhood of this fate is simply connected. This notion is formalized, following [RV], by introducing the width rho(psi) of the embedding psi. It is shown that embeddings with rho(psi) greater-than-or-equal-to 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.