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}\left\lfloor \frac{ n}{ 2}\right\rfloor \left\lfloor\frac{ n-1}{ 2}\right\rfloor \left\lfloor \frac{ n-2}{ 2}\right\rfloor\left\lfloor \frac{ n-3}{ 2}\right\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,\ldots,v_ s\}$ of the vertices and a region $R$ of $D$ with the following property: For all $1 \leq i < j \leq s$, if $D_{ ij}$ is the drawing obtained from $D$ by removing $v_1,v_2,\ldots v_{ i-1},v_{ j+1},\ldots,v_{ s}$, then $v_i$ and $v_j$ are on the boundary of the region of $D_{ ij}$ that contains $R$. For $ s\geq 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\geq 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.
Categories: math.CO cs.CG