Researches Of Graph Embedding On Surfaces With Small Genus

How to imbed a graph into surfaces is a very important researching di-rection in topological theory. Many scholars have done researching work on it. Especially, Computing the number of imbeddings on surfaces with different genus had been an important problem which is called genus distributions or total genus distributions of a graph.Recently, Many new results have been known by using the imbedding model of joint tree which professor Yanpei Liu introduced. Fixing a spanning tree of a graph G, we get the joint tree of graph G by cutting every co-tree edge into two edges. Starting at a vertex, we trace all the edges of joint tree according to the rotation systems and T. Then we write down the letters of co-tree edges in order. It is the associated surface of G. There are one to one relationship between the associated surfaces and its imbeddings.It has been known that imbedding distribution is a NP-problem. For many graphs, we haven't known its imbedding distributions and total imbedding dis-tributions yet. However, there is always relation among the imbeddings on surfaces of different genus. Therefore, it has significance to the study of imbed-dings on some surfaces. In particular, it is important for investigating on the imbedding on sphere, torus, projective plane, Klein bottle. In this thesis, we research on the imbeddings of some graphs on surfaces with small genus, es-pecially on projective plane. In the following, we will introduce the content of each chapter briefly.In Chapter 1, we firstly state the concept of surface, imbedding and how to represent surfaces by polygons. Then we introduce the very important results and theory system of graph imbedding. In the following, the background of this thesis is presented.In Chapter 2, we firstly introduce the imbedding model of joint tree. Then some important lemmas or theorems are introduced or proved. It includes the polygonal representations of projective plane and Klein bottle.In Chapter 3, we study the imbedding of circular multi-ladders on the projective plane. The imbedding number and properties are known.In Chapter 4, we study the imbedding of two types graphs of necklaces. We get its imbedding number on sphere, torus, projective plane and Klein bottle. We also find out the relationship between their imbedding and the according imbedding of bouquets of circles and dipoles.In Chapter 5, we study on the embedding number of circular graph C(2n,2) on the projective plane.In Chapter 6, we study on the embedding number of circular graph C(2n+ 1,2) on the projective plane.In Chapter 7, we firstly summarize the results of this thesis. Then we prospect the future research work.