The 2-page crossing number of $K_{n}$

B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar

Abstract:

Around 1958, Hill conjectured that the crossing number $cr(K_n)$ of the complete graph $K_{n}$ is

$$Z\left( n\right):=\frac{1}{4}\left\lfloor \frac{n}{2}\right\... ...ac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$$

and provided drawings of $K_{n}$ with exactly $Z(n)$ crossings. Towards the end of the century, substantially different drawings of $K_{n}$ with $Z(n)$ crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line $\ell$ (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by $\ell$. The 2-page crossing number of $K_{n}$, denoted by $\nu_{2}(K_n)$, is the minimum number of crossings determined by a 2-page book drawing of $K_{n}$. Since $cr(K_n) \le \nu_2(K_n)$ and $\nu_2(K_n) \le Z(n)$, a natural step towards Hill's Conjecture is the (formally) weaker conjecture $\nu_2(K_n) = Z(n)$, that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of $K_n$, and use it to prove that $\nu_{2}(K_n) = Z(n)$. To this end, we extend the inherent geometric definition of $k$-edges for finite sets of points in the plane to topological drawings of $K_{n}$. We also introduce the concept of ${\leq}{\leq}k$-edges as a useful generalization of ${\leq}k$-edges. Finally, we extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of $K_{n}$ in terms of its number of $k$-edges to the topological setting.

Reference: B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar. The 2-page crossing number of $k_{n}$. In $28^{th}$ Ann. ACM Symp. Computational Geometry, pages 397-403, Chapel Hill, NC, USA, 2012.