New bounds on crossing numbers (Q1591053)

The notation \(f(n)\ll g(n)\) means that, as \(n\) goes to infinity, \(g(n)/f(n)\) goes to infinity also. For \(g\geq 0\), let \(S_g\) denote the closed orientable 2-manifold of genus \(g\), with \(\text{cr}_g(G)\) the minimum number of crossing points among all drawings of the graph \(G\) on \(S_g\). Finally, let \(\kappa_g(n,e)\) be the minimum \(\text{cr}_g(G)\), over all graphs \(G\) of order \(n\) and size at least \(e\). The authors show that, if \(n\ll e\ll n^2\), then the limit, as \(n\) goes to infinity, of \(\kappa_g(n, e)n^2/e^3\) is a positive constant \(C\) (independent of \(g\)). The case \(g= 0\) affirms a conjecture of \textit{P. Erdős} and \textit{R. K. Guy} [Am. Math. Mon. 80, 52-68 (1973; Zbl 0264.05109)]. The present authors also show that if \(G\) has order \(n\) and size \(e\geq 4n\), but no 4-cycle (respectively no 6-cycle), then \(\text{cr}_0(G)\geq ce^4/n^3\) (respectively \(ce^5/n^4\)), for a suitable constant \(c> 0\).