The k-planar crossing number of random graphs and random regular graphs

Abstract

We give an explicit extension of Spencer's result on the biplanar crossing number of the Erdos-Renyi random graph $G(n,p)$. In particular, we show that the k-planar crossing number of $G(n,p)$ is almost surely $\Omega ((n^{2}p{)}^2)$. Along the same lines, we prove that for any fixed $k$, the $k$-planar crossing number of various models of random $d$-regular graphs is $\Omega ((dn{)}^2)$ for $d>c_0$ for some constant $c_0=c_0(k)$.