Does there exist a sequence of graphs $\{ G\_n \}$ such that


1. $G\_n$ has $n$ vertices,
2. the number of edges of $G\_n$ is $O(n)$, and
3. the crossing number of $G\_n$ is $\Omega(n)$?


In particular, do random $k$-regular graphs satisfy this?


Motivation: the crossing number inequality gives a lower bound on the crossing number $cr(G)$, just in terms of the number of vertices $v$ and edges $e$. In particular, if $e \ge 4v$ then
$$ cr(G) \ge \frac{e^3}{64v^2}.$$
This is tight, up to a constant factor, meaning there are graphs whose crossing numbers are approximately this small. But this still raises the question of how large the crossing number can be, particularly for sparse graphs. 



Do there exist sparse graphs with large crossing number?
Take the following graph: start with the complete graph $K\_5$, and replace every edge by $n/10$ paths of length $2$. The resulting graph has $n+5$ vertices, $2n$ edges, and crossing number $n^2/100$.


For random graphs with expected number of edges $e>10n$, [Pach and Tóth](http://www.renyi.hu/~pach/publications/13problems.ps) showed that their crossing number is at least $e^2/4000$ almost surely.




---


**Edit:** In fact, the following graphs also satisfy the conditions 1-3, although they are not sparse: a complete graph with $2\sqrt{n}$ vertices together with $n-2\sqrt{n}$ isolated vertices has $n$ vertices, less than $2n$ edges, and more than $n^2/5 - O(n^{3/2})$ crossings. 


(The constant $1/5$ in this last lower bound follows from the currently best known lower bound $0.8594 n^4/64 - O(n^3)$ on the crossing number of the complete graph by [Klerk et al.](http://link.springer.com/article/10.1007%2Fs10107-006-0039-7) They proved a lower bound for the complete bipartite graph, but a lower bound for $K\_n$ follows by a straightforward double-counting argument.)


