Nedela, R.; Skoviera, M. 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 Cited in 3 ReviewsCited in 6 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:maximum genus; upper-embeddable Citations:Zbl 0698.00017 PDFBibTeX XML