Improved Lower Bounds on Book Crossing Numbers of Complete Graphs
Etienne de Klerk, Dmitrii V. Ṗasechnik, Gelasio Salazar · SIAM Journal on Discrete Mathematics · 2013
A book with $k$ pages consists of a straight line (the spine) and $k$ half-planes (the pages), such that the boundary of each page is the spine. If a graph is drawn on a book with $k$ pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a $k$-page drawing). The $k$-page crossing number $ u_k(G)$ of a graph $G$ is the minimum number of crossings in a $k$-page drawing of $G$. In this paper we investigate the $k$-page crossing numbers of complete graphs. We use semidefinite programming techniques to give improved lower bounds on $ u_k(K_n)$ for various values of $k$. We also use a maximum satisfiability reformulation to obtain a computer-aided calculation of the exact value of $ u_k(K_n)$ for several values of $k$ and $n$. Finally, we investigate the best construction known for drawing $K_n$ in $k$ pages, calculate the resulting number of crossings, and discuss this upper bound in light of the new results reported in this paper.