×

On graphs embeddable with short faces. (English) Zbl 0705.05027

Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 519-529 (1990).
[For the entire collection see Zbl 0698.00017.]
A graph is upper-embeddable if it embeds on some orientable surface with either one or two faces. Equivalently, an upper-embeddable graph has maximum (orientable) genus \(\lfloor \beta /2\rfloor\), where \(\beta\) is the Betti number. It is known that any graph which triangulates a surface (orientable or nonorientable) is upper-embeddable. The authors prove here that any graph which embeds on a surface (orientable or nonorientable) such that no face is of length five or more is upper-embeddable. This result confirms that most complete and complete bipartite graphs are upper-embeddable. It has the interesting corollary that any embedding of any non-upper-embeddable graph must have a face circuit of length at least 5.
The proof uses a result of Payan and Xuong that any cyclically 4-edge- connected graph is upper-embeddable, together with a careful inductive analysis of cycle-separating cuts with at most 3 edges.
Reviewer: D.S.Archdeacon

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0698.00017