
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\).
Extremal problems in graph theory, crossing points, 2-manifold of genus, Planar graphs; geometric and topological aspects of graph theory, drawings
Extremal problems in graph theory, crossing points, 2-manifold of genus, Planar graphs; geometric and topological aspects of graph theory, drawings
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 30 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
