Classification Of Graph Embeddings On Surfaces

In this thesis,we study the classification of graph embeddings on surfaces that is to determine the number of(nonequivalent) embeddings of graph on surfaces.It is an important problem in the study of graph embedding in topological graph theory.The graphs here are all connected graphs and the surface is a compact 2-dimensional manifold without boundary.An embedding of a graph G into a surface S is a homeomorphism h:G→S of G into S such that every component of S - h(G) is a 2-cell.In this thesis,this type of embedding is also called general embedding.Two embeddings h:G→S and g:G→S of G into a surface S are said to be equivalent if there is a homeomorphism f:S→S such that f o h = g.Research on this problem can be tracked back to 1987 when J.L.Gross and M.L.Furst were studying the hierarchy for embedding invariants of a graph,then it has been developed and deepened by many people.In this thesis,the embeddings we discussed include general embeddings,weak embeddings and strong embeddings.A weak embedding is an embedding with no repeated edges on the boundary of each face of it.A strong embedding is an embedding with no repeated vertices on the boundary of each face of it.There is no result about the number of weak(or strong) embeddings of graphs on surfaces as we known up to now,except the results here.The surfaces that we concerned are mainly surfaces of small genus,include the sphere,torus,double torus,projective plane,Klein bottle,nonorientable surfaces of genus 3 and 4.The numbers of embeddings on surfaces of higher genera depend on those of lower genera,so it will be helpful for the further research of embeddings on surfaces of higher genera.The graphs we studied,such as wheel graph,bouquets of circles etc are all important graphs in topological graph theory.And in this thesis,the total genus distribution which shows the genus distribution on both orientable and nonorientable surfaces, of some classes of graphs are also obtained.In the following,We will introduce the content of each chapter of this thesis briefly.In Chapter 1,firstly,we give a brief introduction on concepts and background of graph embedding.Then we introduce the polygonal representations and algebraic representations of surfaces,topological operations on surfaces and the classifi- cation of surfaces.The joint tree model of graph embedding which was established by professor Liu Yanpei and used in this thesis are also described in detail.Finally, We introduce the structure and the content of each chapter of this thesis briefly.In Chapter 2,we study the numbers of embeddings of wheel graphs on some surfaces of small genera,the numbers of embeddings of wheel graphs on the torus, double torus,nonorientable surfaces of genus 1,2,3 and 4 are obtained.And we also obtain the numbers of embeddings of dipoles on the nonorientable surfaces of genus 1-4.In Chapter 3,we study the numbers and the structures of embeddings of bouquets of circles on the projective plane and Klein bottle,simplify the known results greatly.In Chapter 4,we define a class of more complex graph based on wheel graph, and call it as pseudowheels.The numbers of three types of embeddings,i.e., general embeddings,weak embeddings and strong embeddings,of pseudowheels on the projective plane are obtained.In Chapter 5,the numbers of two types of embeddings,i.e.,general embeddings and strong embeddings,of circular ladders and M(o|¨)bius ladders on the projective plane and Klein bottle are obtained.In Chapter 6,We obtain the total genus distribution of a class of 4-regular graphs.And we deduce the total genus polynomials of two classes of graphs which had been done,these results are in much simpler forms in this thesis.In Chapter 7,some applications from the above conclusions on the flied of enumeration of maps are given.The numbers(nonisomorphic) of rooted one-vertex maps on the projective plane and Klein bottle are deduced and the numbers of (nonisomorphic)(p,q,n)-dipoles on the projective plane and Klein bottle are given.In Chapter 8,we posed some questions for further study,such as the total genus distribution of wheel graph and the explicit expression of total genus polynomial for bouquets of circles,etc.