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}{cc}{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\ge 4$, $T(L_n)$ is not less than $5$ and prove that $T(L_n)=4$ for $n\ge 3$.