Improving the crossing lemma by finding more crossings in sparse graphs
János Pach, Radoš Radoičić, Gábor Tardos, Gézá Tóth · 2004
Twenty years ago, Ajtai, Chvatal, Newborn, Szemeredi, and, independently, Leighton discovered that the crossing number of any graph with v vertices and e>4v edgesis at least ce3/v2, 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 tightup 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 on their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most 3 others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least 73e - 253(v-2). Both bounds are tight up to anadditive constant (the latter one in the range 4v ≤ e ≤ 5v).