Maximum Genus Embeddings and Genus Embeddings on Orientable Surfaces

Abstract

In this paper, the estimations of maximum genus orientable embeddings of graphs are studied, and an exponential lower bound for such numbers is found. Moreover, such two extremal embeddings (i.e., the maximum genus orientable embedding of the current graph and the minimum genus orientable embedding of the complete graph) are sometimes closely related to each other. As applications, we estimate the number of minimum genus orientable embeddings for the complete graph by estimating the number of maximum genus orientable embeddings for the current graph.