Maximum Genus Embeddings and Genus Embeddings on Orientable Surfaces 1

摘要

In this paper, the estimations of maximum genus orientable embeddings of graphs are studied, and an exponential lower bound for such numbers are 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 with each other. As applications, we estimate the number of the minimum genus orientable embeddings for complete graph, by estimating the number of maximum genus orientable embedings for current graph.