On the pagenumber of complete bipartite graphs (Q1386481)

An embedding of a simple graph \(G\) into a book is a placing of the vertices of \(G\) along the spine of the book together with a placing of the edges on the pages such that there is no page with crossing edges. The pagenumber \(p(G)\) is the minimum of pages within which \(G\) can be book embedded. Let \(K_{m,n}\) be the complete bipartite graph. The authors prove that for \(m\geq n\geq 3\) \[ p(K_{m,n})\leq \min\Biggl\{\Biggl\lceil{nr^2+ r+ m\over r^2+ r+ 1}\Biggr\rceil: r\text{ positive integer}\Biggr\} \] and that \[ \min\{m: p(K_{m,n})= n\}= {n^2\over 4}+ O(n^{7/4}). \] In particular, they disprove conjectures of \textit{D. J. Muder}, \textit{M. L. Weaver} and \textit{D. B. West} in [Pagenumber of complete bipartite graphs, J. Graph Theory 12, No. 4, 469-489 (1988; Zbl 0662.05020)].