On the Pagenumber of k -Trees
Jennifer Vandenbussche, Douglas B. West, Gexin Yu · SIAM Journal on Discrete Mathematics · 2009
A p-page embedding of a graph G is a vertex-ordering $\pi$ of $V(G)$ (along the “spine” of a book) and an assignment of edges to p half-planes (called “pages”) such that no page contains crossing edges (alternating endpoints) relative to $\pi$. The pagenumber of G is the least p such that G has a p-page embedding. We disprove a conjecture of Ganley and Heath by showing that when $k\geq3$, there are k-trees that do not embed in k pages. We also present an algorithm that produces k-page embeddings for k-trees in a special class.