The 2-page crossing number of

Around 1958, Hill conjectured that the crossing number

of the complete graph $K_{n}$ is

$\begin{displaymath}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 \end{displaymath}$

and provided drawings of $K_{n}$ with exactly

crossings. Towards the end of the century, substantially different drawings of $K_{n}$ with

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

, and use it to prove that $\nu_{2}(K_n) = Z(n)$ . To this end, we extend the inherent geometric definition of

-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

-edges to the topological setting.

The 2-page crossing number of

Abstract:

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