Graphs with small book thickness
Open access
Publication metrics
PlumX, opens in new tab
Abstract
In an article published in 1979, Kainen and Bernhart [1] laid the groundwork for further study of book embeddings of graphs. They define an n-book as a line L in 3-space, called the spine, and n half-planes, called pages, with L as their common boundary. An n-book embedding of a graph G is an embedding of G in an n-book so that the vertices of G lie on the spine and each edge of G lies within a single page so that no two edges cross. The book thickness bt(G) or page number pg(G) of a graph G is the smallest n so that G has an n-book embedding. Finding the book thickness of an arbitrary graph is a difficult problem. Even with a pre-specified vertex ordering, the problem has been shown to be NP-complete [6]. In this paper we will introduce book embeddings with particular focus on results for graphs with small book thickness.
Publication metrics
PlumX, opens in new tab
Bibliographic Information
Output type
Original language
EnglishPages from-to (Number of pages)
Pages 121-130 (10 pages)Journal (Volume, Issue Number)
Missouri Journal of Mathematical Sciences (Volume 19, Issue 2)Publication milestones
- Published - 2007
Publication status
ISSN
0899-6180Publication IDs
- Scopus: 36048964573
