On Orientable Embedding Genus Distribution Of A Graph

Given a connected graph G and a surface S (a 2-dimensional compact manifold without boundary), if there is a homeomorphism φ such that each connected component of S—φ(G) is homeomorphic to an open disc, then φ(G) is an embedding (in early references 2-cell embedding) on S. If S is orientable, then the embedding is orientable. If S is nonorientable, then the embedding is nonorientable. How to embed a graph on a surface, which is a central problem of topological graph theory. Through this thesis a graph, a surface and an embedding are always implied a connected graph, an orientable surface and an orientable embedding respectively.Given a graph G, the genus of G is the minimum genus of the surface which it can be embedded on. How many distinct embeddings does a graph have on each surface? This is the problem of embedding genus distribution for a graph. Since to determine the genus of a graph is NP-complete, it is more difficult to determine the embedding genus distribution of a graph from this point. It is also significant to determine the embedding genus distribution of a graph.Gross and Furst investigated the embedding genus distribution of a graph in 1987. Until now the embedding genus distribution only for the closed-end ladders, circular ladders, M(o|¨)bius ladders, Ringel ladders, dipoles, cobblestone paths, bouquets of circles and necklaces are determined. They mainly used the combinatorial method, a formula of Jackson and overlap matrices of Mohar to calculate the embedding genus distribution of a graph. However, the above methods are rather limited for the embedding genus distribution in general.Liu created joint trees, initiated in his early paper in 1979, of a graph in 2003 which provided a foundation on studying embedding genus distribution.In this thesis we introduce embedding surfaces of a graph and the genus distribution of a surface set. We extract embedding surfaces of a graph by using joint trees of the graph. Then we develop two new methods. One is a surface generating method which calculates the embedding genus distribution of a graph by using the...