## DIMACS TR: 99-37

## New Bounds on Crossing Numbers

### Authors: János Pach, Joel Spencer and Géza Tóth

**
ABSTRACT
**

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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-37.ps.gz

DIMACS Home Page