Research On Book Embedding Problem Of Some Types Of Graphs

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other.We call the minimum number of subsets of a page partition P the pagenumber of G under labeling f.and denote it by pn(G,f).The pagenumber of G is defined as pn(G)=min pn(G,f),where f is taken over all labeling of G.Book embedding is an important research content of topological graph theory,and has applications in data transmission,network design,traffic flow and other areas.In this paper,we investigate the relationship between pagenumber and Lovász number firstly and generalize De Klerk E's some results to general case.A suf-ficient condition is obtained to find a lower bound of pagenumber of a graph by Lovász number.Then we apply it to the book embedding of the Cartesian product of a complete graph Km and a path P2.Then we further study the pa-genumber of the Cartesian product of complete graph and path pn(Km×Pn),the pagenumber of the Cartesian product of complete graph and cycle pn(Km×Cn),and get some accurate values and upper bounds.Secondly,we consider the pagenumber of the complete expansion graph ?c(G)of G.We get the relationship between the pagenumber of the complete expansion graph of the subgraph and the pagenumber of the complete expansion graph of the supergraph.For any simple graph G,the pagenumber of ?c(G)is related to the maximum degree of G and pagenumber of G.We get the upper bound and the lower bound of the pagenumber of ?c(G).For the complete expansion graph of some special graphs,such as star graph Sm,tree T,Mobius Ladder Mh,Petersen graph P and complete graph K2m,the exact pagenumbers of them are obtained.Finally,we study the book embedding of trivalent 1-planar graphs and get that 1-planar graphs with maximum degree 3 can be embedded in 4 pages.