Graphs Embedded With Crossing Number

This paper mainly studies embeddings of graphs and their crossing numbers.Chapter 1 is devoted to basic concepts of embeddings and crossing numbers of graphs.In chapter 2, we prove the generalized permutation graph G(n, k) with no more than two subcycles whose length are odd number is upper embeddable, and show the probability that the maximum genus of G(n, k) is no less than tends to 1 when k - .In chapter 3, we prove the generalized Peter sen graph P(n, m) is upper embeddable, and show that the Euler genus of P(2m + 1,m)(m > 3) is 1. Also, we show that the Euler genus of P(2m + 2,m)(m > 4) is 2.Chapter 4 provides an upper bound for crossing number of circular graphs using their 2-cell embeddings in the torus. Simultaneously, crossing numbers of circular graphs C(2m, m)(m > 3), C(2m +1, m) and C(2m + 2, m)(m > 3) are determined as 1,1 and m + 1, respectively.