Does there exist a sequence of graphs $\{ G_n \}$ such that
- $G_n$ has $n$ vertices,
- the number of edges of $G_n$ is $O(n)$, and
- 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.