On the crossing number of complete graphs
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser · 2002
(MATH) Let $\overlinecr(G)$ denote the rectilinear crossing number of a graph $G. We determine $\overlinecr(K 11)=102 and $\overlinecr(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.(MATH) Based on these findings, we establish new upper and lower bounds on $\overlinecr(K n), for general n. Specific values are given for n, ≤ 45. The new asymptotic lower bound is immediate from the result $\overlinecr(K 11)=102, whereas the upper bound stems from a novel construction of drawings with few crossings. The tantalizing question of determining $\overlinecr(K 13) is left open. The latest ra(n)ge is 221,223,225,227,229; our conjecture is $\overlinecr(K 13) = 229.