The Book Embedding Of Special Graphs

A book comprises a spine and some number of pages.A spine can be seen as a line and each of the page can be seen as a half-plane with spine as its boundary.The problem of book embedding of a graph can mainly be divided into two steps,the first step is setting the vertices on the spine and the second step is assigning edges to the half planes so that edge assigned to the same page is not crossing.The page number and the page width are the two indexes to measure the quality of a book embedding,the problem of a book embedding is to find the optimal book embedding about the page number or the page width.In this paper,we mainly use the page number to measure the quality of a book embedding of graph G,which is the minimum number that G can be embedded.Given a simple graph G=(V,E)with n vertices and a bijection f:V?1,2,…,n,where f(v)? {1,2,…,n} represents the labeling of G.If two edges uv,xy satisfy f(u)<f(x)<f(v)<f(y)or f(x)<f(u)<f(y)<f(v),then we called the two edges are crossing.Let ui=f-1(i),then f can be regarded as the linear ordering of the vertices on the spine.For the given labeling f,if the edges in any subset Ei,i=1,2,…,p are not crossing with each other,then we call the partition(?)={E₁,E₂,…,E_p} of edge set E is the page partition of E(G).So,the page partition(?)also can be seen as the edge set partition of graph G.We call the mini number of p is the page number based on f,denoted by p(G,f).Then the page number of graph G is P(G)=min f p(G,f),where f is taken over all labeling of graph G.Furthermore,if k?p(G),then we say graph G is k page embeddable.In this paper,we mainly study the book embedding of the graph bundle with cycles and stars,the lexicographic product of paths and stars,the line and total graphs of some special graphs.For the book embedding of graph bundles,when the product operation is cartesian product or tensor product,we obtained the exact results except one special case.For the book embedding of line and total graphs,we obtained the necessary and sufficient conditions of the page number of line graph of planar graph and also obtained the lower bound of page number of total graph by utilizing the relation of a graph and its line and total graph.