On Graphs Embeddable with Short Faces
Roman Nedela, Martin Škoviera · 1990
Genus embeddings of graphs whose genus is known are, for the most part, either triangular or quadrilateral, or differ from these in several exceptional faces. In order to determine all orientable surfaces in which such graphs have 2-cell embeddings it is sufficient to compute their maximum genus. So far, it has been known that every graph which triangulates some closed surface is upper embeddable, that is, its maximum genus is equal to [ β /2], where β is its Betti number (Khomenko and Glukhov [2], Nebeský [3]). The main objective of the present paper is to generalize this result. We shall show that every graph admitting a 2-cell embedding in in some closed surface so that the length of every face does not exceed four is upper embeddable. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.