The 2-page crossing number of $K_n$

Around 1958, Hill described how to draw the complete graph $K_n$ with [Z(n) :=1/4\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}% \rfloor \lfloor \frac{n-3}{2}\rfloor] crossings, and conjectured that the crossing number $\crg (K_{n})$ of $K_n$ is exactly Z(n). This is also known as Guy's conjecture as he later popularized it. Towards the end of the century, substantially different drawings of $K_{n}$ with Z(n) crossings were found. These drawings are \emph{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 \emph{2-page crossing number} of $K_{n}$, denoted by $ν_{2}(K_{n})$, is the minimum number of crossings determined by a 2-page book drawing of $K_{n}$. Since $\crg(K_{n}) \leν_{2}(K_{n})$ and $ν_{2}(K_{n}) \le Z(n)$, a natural step towards Hill's Conjecture is the %(formally) weaker conjecture $ν_{2}(K_{n}) = Z(n)$, popularized by Vrt'o. %As far as we know, this natural %conjecture was first raised by Imrich Vrt'o in 2007. %Prior to this paper, results known for $ν_2(K_n)$ were basically %the same as for $\crg (K_n)$. Here In this paper we develop a novel and innovative technique to investigate crossings in drawings of $K_{n}$, and use it to prove that $ν_{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 and extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of $K_{n}$ in terms of its number of $(\le k)$-edges to the topological setting.

No reviews yet.

No comments yet.