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 (order types) of size
on these findings, we establish a new upper bound on
. The bound stems from a novel construction of drawings of
with few crossings.
Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser.
On the crossing number of complete graphs.
Computing, 76:165-176, 2006.