In 1958, Hill conjectured that the minimum number of crossings in a
drawing of K_n is exactly Z(n) = 1/4 n/2 [(n‚àí1)/2] [(n‚àí2)/2] [ (n‚àí3)/2] .
Generalizing the result by Ábrego et al. for
2-page book drawings, we prove this conjecture for plane drawings
in which edges are represented by x-monotone curves. In fact,
our proof shows that the conjecture remains true for x-monotone
drawings of K_n in which adjacent edges may cross an even number
of times, and instead of the crossing number we count the pairs of
edges which cross an odd number of times. We also introduce a
combinatorial characterization of x-monotone drawings of
complete graphs, which is suitable for computer calculations.
Joint work with Martin Balko and Jan Kynčl.