The Embedding Genus Of Some Kinds Of Graphs

In this thesis, we study the embedding of some kinds of graphs. A compact ori-entable2-manifold is an orientable surface(non-orientable surface) that may be thought of as a sphere on which has been placed a number of handles(crosscaps). A graph is embedded on a surface S if it is drawn on S so that edges intersect only at their common end vertices. An embedding of a graph G on a surface S is a2-cell embedding if all em-bedded regions are isomorphic to an open disk. The γ(G)(γ(G)) of a graph G is meant the minimum genus of all possible orientable surfaces(nonorientable surfaces) on which G can be embedded with no edge crossings, similarly, the γM(G)(γM(G))is the maxi-mum genus. The planer graphs have genus zero since no handles are needed to prevent edge intersections. Noted that gi(gi) is the orientable(nonorientable) genus of orientable surface SI(nonorientable surface Ni), i≥0(i≥1), then gγ(g),gγ(G)+1,...,gγM(G)(gγ(G),gγ(G)+1,...,gγM(G)) is the genus distribution or embedding distribution of a graph G on an orientable(non-orientable) surface. As a measure of the complexity of a network, the genus gives an indication of how efficiently the network can be laid out. The smaller the genus, the more efficient the layout.In the first chapter, the origination and development of a graph embedding are reviewed, and then related conceptions, theories and some conclusions are introduced.In the second chapter, based on the structure of the balanced hypercube, we com-pute the genus of a balanced hypercube. After that we derive the genus of the folded hypercube.In the third chapter, using the overlap matrix, we give the genus distribution of a circular-like graph on orientable surfaces.In the forth chapter, the number of different embeddings on projective planes for a kind of generalized petersen graphs and a juxtaposition of star graphs are given and be proved by different ways.In the last chapter, the conclusions and future works are presented.