| The maximum genus of a connected graph is defined to be the maximum integer g for which the graph has a cellular embedding in an orientable surface of genus g. We present the two most popular methods used to determine the maximum genus of a connected graph, contributed by Xuong and Nebesky, survey the polynomial-time algorithms available for finding a maximum genus embedding, and discuss the shortcomings of those algorithms.;We develop new results on the relationship between maximum genus and maximum matchings on intersection graphs, of spanning trees and cotrees, and introduce a new class of intersection graphs, called facial intersection graphs, defined for a given plane embedding. We show that for particular planar 2-connected graphs and for embeddings with certain properties, we can calculate the maximum genus using a standard matching algorithm on an optimal facial intersection graph. |
