New bounds on crossing numbers
type: Item
instance of: scholarly article
title: New bounds on crossing numbers
zbMATH Open document ID: 0963.05038
published in: Discrete \& Computational Geometry
publication date: 2001-06-28T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1545819
zbMATH Keywords: 2-manifold of genus
zbMATH Keywords: crossing points
zbMATH Keywords: drawings
author: János Pach
author: Joel Spencer
author: Géza Tóth
reviewed by: Arthur T. White
MaRDI profile type: Publication
full work available at URL: s004540010011
OpenAlex ID: W4249905773
DOI: 10.1007/S004540010011
description: scientific article; zbMATH DE number 1545819