Topological Operations for Genus Distributions and Embeddings of Graphs

The research of graph embeddings on surfaces started from Euler's equation v e+f = 2. For a connected graph G, v, e and f represent the number of vertices, edges and regions of an embedding on a plane or sphere. Genus embedding of graphs is one of the most studied subjects in topological graph theory. A polynomial is used to represent a graph's embedding distribution on di erent surfaces which are classi ed by genus. We discuss orientable genus embeddings of connected undirected graphs which are derived from some other graphs by topological operations, including face-contraction, vertexsplitting, vertex-augment, pearl-making, bouquet-making and face-expansion which are designed to treat one graph. We then consider the Cartesian product, dot product and extended dot product which are designed to be applied between two graphs. Face-contraction, vertex-splitting, vertex-augment, pearl-making, bouquet-making and face-expansion are discussed to achieve partial genus distribution of some graphs, including fan graph Fn, cube-connected cycles CCCn and star-connected cycles SCCn. For several in nite families of graphs, we calculate their minimum and maximum genus and demonstrate constructions of embeddings of all genera between these ranges. The graphs discussed in the thesis are derived from Cartesian product, dot product and a newly de ned extended dot product.