
book embedding
Book Thickness of Subdivisions ★★
Author(s): Blankenship; Oporowski
Let be a finite undirected simple graph.
A -page book embedding of
consists of a linear order
of
and a (non-proper)
-colouring of
such that edges with the same colour do not cross with respect to
. That is, if
for some edges
, then
and
receive distinct colours.
One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.
The book thickness of , denoted by bt
is the minimum integer
for which there is a
-page book embedding of
.
Let be the graph obtained by subdividing each edge of
exactly once.
Conjecture There is a function
such that for every graph
,



Keywords: book embedding; book thickness
