The Book Embedding Of Given Graphs

A book consists of a spine that is just a line and some number of pages each of which is a half-plane with the spine as boundary.The book embedding of a graph G is divided into two steps,first,all vertices of the graph are arranged on the spine according to a certain sequence L(spine sequence).For convenience,we map the vertices on one by one to {1,2,· · ·,n};then assign each edge of the graph to a single page so that the edges of the same page are not intersected with each other.Under the sequence L of spine,if the two edges(a,b)and(c,d)of the same page are intersected,then their order must satisfy L(a)< L(c)< L(b)< L(d)orL(c)< L(a)< L(d)< L(b).Pagenumber and pagewidth are two indicators to measure the quality of book embedding.Among them,the pagenumber pn(G) is the minimum number of pages that can be embedded in the graph G;pagewidth is the maximum number of edges that intersect any half-line perpendicular to the spine in the page,but the pagewidth of the graph G is the minimum pagewidth of any book embedding of G.The optimal embedding of a graph is an embedding with one or both of the two indicators as objectives.In this paper,the problem of book embedding is studied with pagenumber as a single objective,That is to find the minimum value that a graph can be embedded in pagenumber.In this paper,we mainly study the problem of book embedding of Cartesian product graphs,semi-strong product graphs,Cartesian product bundles and three hypercube variants.For Cartesian product bundles,the exact pagenumber is determined except for individual cases.For other types of graphs,the upper and lower bounds of the pagenumber are obtained,and in some special cases,the exact number of pages is obtained.