Georgia Institute of Technology College of Sciences

The crossing number of a graph is the minimum number of crossings it can be drawn in a plane. Let $\kappa(n, m)$ be the minimum crossing number of graphs with $n$ vertices and (at least) $m$ edges. Erd\H{o}s and Guy conjectured and Pach, Spencer and T\'oth proved that for any $m = m(n)$ satisfying $n \ll m \ll n^2$, the quatity $\ds\lim_{n \to \infty} \frac{\kappa(n,m) n^2}{m^3}$ exists and is positive. The $k$-planar crossing number of a graph is the minimum crossing number obtained when we partition the edges of the graph into $k$ subgraphs and draw them in $k$ planes. Using designs and a probabilistic algorithm, the guaranteed factor of improvement $\alpha_k$ between the $k$-planar and regular crossing number is $\frac{1}{k^2} (1 + o(1))$, while if we restrict our attention to biplanar graphs, this constant is $\beta_k = \frac{1}{k^2}$ exactly. The lower bound proofs require the existence of a midrange crossing constant. Motivated by this, we show that the midrange crossing constant exists for all graph classes (including bipartite graphs) that satisfy certain mild conditions. The regular midrange crossing constant was shown to be is at most $\frac{8}{9\pi^2}$; we present a probabilistic construction that also shows this bound.