The Numbers Of Embedding Of Certain Kinds Of Graphs On Surfaces

In this thesis, we study the embeddings of graphs on surfaces that is important problem in the topological graph theory.In this thesis, the embedding we discussed is general celluar embeddings, the sur-faces that we concerned are nonorientable surfaces of small genus, include the projec-tive and Klein bottle and orientable surfaces. The number of embeddings on surfaces of higher genera depend on the lower genera, so it will be helpful for the further research of embedding on the higher genera. The generalized petersen graphs we studied are one of important kind of graphs in the topological graph theory. In this paper, the em-bedding numbers of one kind of generalized petersen graphs on nonorientable surfaces of small genus are given. Furthermore the genus distributions of one certain graphs on orientable surfaces are derived. In the following, we will introduce the content of each chapter of this thesis briefly.In the first chapter, firstly, we look back the development of the graph theory and introduce the concepts and background of graph embedding. Then we give the details about the polygonal representations and the classification of surfaces, and, algebraic representations of surfaces, topological operations on surfaces. The joint tree model of graph embedding are also introduced in detail. Finally, we introduce the structure and the content of each chapter of this thesis briefly.In the second chapter, based on the joint tree model and the polygonal represen-tations of surfaces, we study the embedding of one kind of the generalized petersen graphs on the projective plane and Klein bottle.In the third chapter, we study the embedding of a type graphs on the orientable surfaces by using the joint tree model, and its genus distribution are obtained.In the fourth chapter, we present the conclusions and the future works.