A Study of Typenumber in Book-Embedding

Abstract

The type of a vertex \(v\) in a \(p\)-page book-embedding is the \(p \times 2\) matrix of nonnegative integers

\[{r}(v) =
\left(
\begin{array}{ccccc}
l_{v,1} & r_{v,1} \\
. & . \\
. & . \\
. & . \\
l_{v,p} & r_{v,p} \\
\end{array}
\right),\]

where \(l_{v,i}\) (respectively, \(r_{v,i}\)) is the number of edges incident to \(v\) that connect on page \(i\) to vertices lying to the left (respectively, to the right) of \(v\). The type number of a graph \(G\), \(T(G)\), is the minimum number of different types among all the book-embeddings of \(G\). In this paper, we disprove the conjecture by J. Buss et al. which says for \(n \geq 4\), \(T(L_n)\) is not less than \(5\) and prove that \(T(L_n) = 4\) for \(n \geq 3\).