Blankenship, Robin


Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $ G $ be a finite undirected simple graph.

A $ k $-page book embedding of $ G $ consists of a linear order $ \preceq $ of $ V(G) $ and a (non-proper) $ k $-colouring of $ E(G) $ such that edges with the same colour do not cross with respect to $ \preceq $. That is, if $ v\prec x\prec w\prec y $ for some edges $ vw,xy\in E(G) $, then $ vw $ and $ xy $ 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 $ G $, denoted by bt$ (G) $ is the minimum integer $ k $ for which there is a $ k $-page book embedding of $ G $.

Let $ G' $ be the graph obtained by subdividing each edge of $ G $ exactly once.

Conjecture   There is a function $ f $ such that for every graph $ G $, $$   \text{bt}(G) \leq f( \text{bt}(G') )\enspace.   $$

Keywords: book embedding; book thickness

Syndicate content