On the Crossing Number of Complete Graphs
O. Aichholzer, F. Aurenhammer, and H. Krasser
denote the rectilinear crossing number of a graph
Despite the remarkable hunt for crossing numbers of the complete graph
- initiated by R. Guy in the 1960s - these quantities have been unknown for
to date. Our solution mainly relies on a tailor-made method for
enumerating all inequivalent sets of points (so-called order types) of size
. Based on these findings, we establish new upper and lower bounds on
. Specific values for
given, along with significantly improved asymptotic values. The asymptotic
lower bound is immediate from the fact
the upper bound stems from a novel construction of drawings with few
crossings. The construction is shown to be optimal within its frame. The
tantalizing question of determining
is left open. The
latest ra(n)ge is
; our conjecture is
Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser.
On the crossing number of complete graphs.
In Proc. Ann. ACM Symp. Computational Geometry, pages 19-24,
Barcelona, Spain, 2002.