Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs

Twenty years ago, Ajtai et al. and, independently, Leighton discovered that the crossing number of any graph with v vertices and e > 4v edges is at least ce³/v², where c > 0 is an absolute constant. This result, known as the "Crossing Lemma," has found many important applications in discrete and computational geometry. It is tight up to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c > 1024/31827 > 0.032. The proof has two new ingredients, interesting in their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most three others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least Both bounds are tight up to an additive constant (the latter one in the range ).