An improvement of the crossing number bound
Bernard Montaron · Journal of Graph Theory · 2005
Abstract 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) ≥ Cm3/n2 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/25 for graphs with m/n2 > 0.291 and n > 22, and C > 1/20 for dense graphs with m/n2 ≥ 0.485. © 2005 Wiley Periodicals, Inc. J Graph Theory