On the Crossing Number of Complete Graphs

O. Aichholzer, F. Aurenhammer, and H. Krasser

Abstract:

Let $\overline{cr}(G)$ denote the rectilinear crossing number of a graph $G$. We determine $\overline{cr}(K_{11})=102$ and $\overline{cr}(K_{12})=153$. Despite the remarkable hunt for crossing numbers of the complete graph $K_n$ - initiated by R. Guy in the 1960s - these quantities have been unknown for $n>10$ to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size $11$. Based on these findings, we establish a new upper bound on $\overline{cr}(K_{n})$ for general $n$. The bound stems from a novel construction of drawings of $K_{n}$ with few crossings.

Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser. On the crossing number of complete graphs. Computing, 76:165-176, 2006.