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

Abstract

In 1958, Hill conjectured that the minimum number of crossings in a drawing of $K_n$ is exactly $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$. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by $x$-monotone curves. In fact, our proof shows that the conjecture remains true for $x$-monotone drawings of $K_n$ in which adjacent edges may cross an even number of times, and instead of the crossing number we count the pairs of edges which cross an odd number of times. We further discuss a generalization of this result to shellable drawings, a notion introduced by Ábrego et al. We also give a combinatorial characterization of several classes of $x$-monotone drawings of complete graphs using a small set of forbidden configurations. For a similar local characterization of shellable drawings, we generalize Carathéodory's theorem to simple drawings of complete graphs.

43 pages, 30 figures; minor changes, three additional references

References in corpus (2)

• Crossing numbers and combinatorial characterization of monotone drawings of $K_n$
• Shellable drawings and the cylindrical crossing number of $K_n$

Cited by in corpus (8)

• Crossing numbers and combinatorial characterization of monotone drawings of $K_n$
• A superlinear lower bound on the number of 5-holes
• Closing in on Hill's conjecture
• On Crossing-Families in Planar Point Sets
• Simple realizability of complete abstract topological graphs simplified
• An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
• Bounding the tripartite-circle crossing number of complete tripartite graphs
• Remarks on the structure of simple drawings of $K_n$