Embedding Cartesian Product of Some Graphs in Books

Abstract

The book embedding of a graph $G$ consists of placing the vertices of $G$ in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect. The number of pages is the minimum number in which the graph can be embedded. In this paper, we study the book embedding of the Cartesian product $P_m\times S_n$, $P_m\times W_n$, $C_n\times S_m$, $C_n\times W_m$, and get an upper bound of their pagenumber.