A study of typenumber in book-embedding

Yen Chi Chen, Hung-Lin Fu*, I. Fan Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The type of a vertex v in a p-page book-embedding is the p × 2 matrix of nonnegative integers τ(v) = (lv,1 ... lv,p rv,1 ... rv,p) where lv,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 typenumber 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 ≥ 4, T(Ln) is not less than 5 and prove that T(L)n) = 4 for n ≥ 3.

Original languageEnglish
Pages (from-to)97-103
Number of pages7
JournalArs Combinatoria
Volume62
StatePublished - 1 Jan 2002

Fingerprint Dive into the research topics of 'A study of typenumber in book-embedding'. Together they form a unique fingerprint.

Cite this