Book crossing numbers of the complete graph and small local convex crossing numbers

Abstract

A $k$-page book drawing of a graph $G$ is a drawing of $G$ on $k$ halfplanes with common boundary $l$, a line, where the vertices are on $l$ and the edges cannot cross $l$. The $k$-page book crossing number of the graph $G$, denoted by ${\nu }_k(G)$, is the minimum number of edge-crossings over all $k$-page book drawings of $G$. Let $G=K_n$ be the complete graph on $n$ vertices. We improve the lower bounds on ${\nu }_k(K_n)$ for all $k\ge 14$ and determine ${\nu }_k(K_n)$ whenever $2<n/k\le 3$. Our proofs rely on bounding the number of edges in convex graphs with small local crossing numbers. In particular, we determine the maximum number of edges that a convex graph with local crossing number at most $\ell$ can have for $\ell \le 4$.

Version 3 changes: Old Section 2.1 was removed as it distracted from the main results ofthe paper. The proof of Theorem 2 was simplified. Section 3.1 was rewritten to explicitly show the constructions. An overview for the proof of Theorem 5 (now Theorem 4) was added, including a flow chart figure