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

Posted by David Wood
updated July 10th, 2021