Shellable drawings and the cylindrical crossing number of $K_n$

Abstract

The Harary-Hill Conjecture States that the number of crossings in any drawing of the complete graph $K_n$ in the plane is at least $Z(n):=\frac{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$. In this paper, we settle the Harary-Hill conjecture for {\em shellable drawings}. We say that a drawing $D$ of $K_n$ is {\em $s$-shellable} if there exist a subset $S=\{v_1,v_2,\dots ,v_s\}$ of the vertices and a region $R$ of $D$ with the following property: For all $1\le i<j\le s$, if $D_{ij}$ is the drawing obtained from $D$ by removing $v_1,v_2,\dots v_{i-1},v_{j+1},\dots ,v_s$, then $v_i$ and $v_j$ are on the boundary of the region of $D_{ij}$ that contains $R$. For $s\ge n/2$, we prove that the number of crossings of any $s$-shellable drawing of $K_n$ is at least the long-conjectured value Z(n). Furthermore, we prove that all cylindrical, $x$-bounded, monotone, and 2-page drawings of $K_n$ are $s$-shellable for some $s\ge n/2$ and thus they all have at least $Z(n)$ crossings. The techniques developed provide a unified proof of the Harary-Hill conjecture for these classes of drawings.

9 pages, 4 figures

References in corpus (1)

• The 2-page crossing number of $K_n$

Cited by in corpus (1)

• Crossing numbers and combinatorial characterization of monotone drawings of $K_n$