The crossing number, ${\mbox {cr}}(G)$, of a graph $G$ is the least number of crossing points in any drawing of $G$ in the plane. Denote by $\kappa(n,e)$ the minimum of ${\mbox {cr}}(G)$ taken over all graphs with $n$ vertices and at least $e$ edges. We prove a conjecture of P. Erd\H os and R. Guy by showing that $\kappa(n,e)n^2/e^3$ tends to a positive constant as $n\rightarrow\infty$ and $n\ll e\ll n^2$. Similar results hold for graph drawings on any other surface of fixed genus.
We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if $G$ is a graph with $n$ vertices and $e\ge 4n$ edges, which does not contain a cycle of length four (resp. six), then its crossing number is at least $ce^4/n^3$ (resp. $ce^5/n^4$), where $c>0$ is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of M. Simonovits.
DIMACS Home Page