Embedding Properties Of Some Graphs On Surfaces

In this thesis, we study the embedding properties of graphs on surfaces, which is an important subject in topological graph theory. Firstly, we give the formulas for computing the flexibility of wheels and wheel-like graphs on the torus. Secondly, we prove some properties of locally LEW-embedded graphs. Moreover, we show that there exist infinite graphs which satisfy the condition of locally LEW-embeddings but not LEW-embeddngs, meanwhile, we prove that there exists, a polynomial time algorithm for finding the shortest contractible cycle in an locally LEW-embedded graph. At last, we discuss the crossing number of some graphs on the projective plane, then we obtain the nonorientable crossing number sequences of those graphs. The results will be given as follows:1. By using Jordan Curve Theorem and classical combination, we obtain the formulas for computing the flexibility of wheels and wheel-like graphs on the torus.2. By C.Thomassen's work on Large Edge Width embeddings, we obtain some properties of some locally LEW-embedded graphs. Together with some basic knowledge of Linear Algebra, we prove that there exists a polynomial time algorithm for finding the shortest contractible cycle in an locally LEW-embedded graph.3. By some results of Minor Theorem, we prove the crossing numbers of some circular graphs C(10,4), C(9,3), C(8,3) on the projective plane. Furthermore, we determine the nonorientable crossing number sequences of those graphs by their crossing numbers on the projective plane and the embedding technique. Then we show that the nonorientable crossing number sequence of C(10,4) is non-convex.