Premium
An improvement of the crossing number bound
Author(s) -
Montaron Bernard
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20090
Subject(s) - combinatorics , mathematics , conjecture , crossing number (knot theory) , graph , upper and lower bounds , constant (computer programming) , plane (geometry) , discrete mathematics , geometry , computer science , mathematical analysis , intersection (aeronautics) , engineering , programming language , aerospace engineering
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