An improvement of the crossing number bound

The crossing number cr ( G ) of a simple graph G with n vertices and m edges is the minimum number of edge crossings over all drawings of G on the ℝ 2 plane. The conjecture made by Erdős in 1973 that cr ( G ) ≥  Cm 3 / n 2 was proved in 1982 by Leighton with C  = 1/100 and this constant was gradually improved to reach the best known value C  = 1/31.08 obtained recently by Pach, Radoicčić, Tardos, and Tóth [4] for graphs such that m  ≥ 103n/16. We improve this result with values for the constant in the range 1/31.08 ≤  C  &< 1/15 where C depends on m / n 2 . For example, C  > 1/25 for graphs with m / n 2  > 0.291 and n  > 22, and C  > 1/20 for dense graphs with m / n 2  ≥ 0.485. © 2005 Wiley Periodicals, Inc. J Graph Theory