Progress on rectilinear crossing numbers
O. Aichholzer, F. Aurenhammer, and H. Krasser
denote the rectilinear crossing number of a graph
the remarkable hunt for the crossing number of the complete graph
initiated by R. Guy in the 1960s, these quantities have been unknown for
to date. We also establish new upper and lower bounds on
, along with an improved
general lower bound for
. The results mainly rely on
recent methods developed by the authors for exhaustively enumerating all
combinatorially inequivalent sets of points (so-called order types).
Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser.
Progress on rectilinear crossing numbers.
Technical report, IGI-TU Graz, Austria, 2002.