Orientable Embedding Genus Distribution For Three Types Of Letter-graphs

This thesis is to discuss genus distribution of embeddings for connected graphs. It belongs to the counting problem of the graph embedding theory. It is used to solve the range of the genus of the embedded surfaces, and the number of distinct embeddings for a graph. The genus distribution can be expressed by genus polynomial, that is f(x)=a₀+a₁x + a₂x² +…+ a_nxⁿ.Here n denotes the maximum genus of the embedded surface, and a_i is the number of the distinct embeddings for genus i.Embedding mentioned here means orientable embedding; Surface is 2-dimensimal compact manifold without boundary; " Distinct" means being not homeomorphic.Particularly, this thesis mainly solve the genus distribution problem of three types of letter-graphs called V_n(n= 0,1,2,…),D_n(n = 0,1,2,…)/O_n(n = 0,1,2,…) and H_n(n = 0,1,2,…).Each type has similar shape and the numbers of their vertexes and edges compose arithmetic series. The basic theory of my thesis is joint tree model for embedding which was created by Liu in 2003;The method used here is called surface generating method. In order to get the genus distribution of the graph considered, we have to do work as follows (Here give V_n(n=0,1, 2,…) for example):1) Calculate the range of the orientable surface's genus that V_n can be embedded;2) Get the joint tree model for V_n;3) Generate the surfaces that V_n can be embedded from that of V_n-1, then sort them by topological equivalence between the surfaces themselves;4) Deduce the genus of the sorted surfaces from which they are generated by the conclusion of 3) and get the relationship of the genus between the orientable surfaces that V_n-2,V_n-1,V_n can be embedded respectively;5) Get the genus polynomial for V_n by the relationship of the genus that can be known from 4).