Using Block Designs in Crossing Number Bounds

The crossing number $\text{mbox}cr(G)$ of a graph $G=(V,E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$,the$k$-planarcrossingnumberof$G$,${\mbox {cr}}_k(G)$, is defined as the minimum of $\text{mbox}cr(G_1)+\text{mbox}cr(G_2)+\dots +\text{mbox}cr(G_k)$ over all graphs $G_1,G_2,\dots ,G_k$ with ${\cup }_{i=1}^k{G}_i=G$. Pach et al. [\emph{Computational Geometry: Theory and Applications} {\bf 68} 2–6, (2018)] showed that for every $k\ge 1$, we have ${\mbox {cr}}_k(G)\le \left(\frac{2}{k^2}-\frac1{k^3}\right){\mbox {cr}}(G)$ and that this bound does not remain true if we replace the constant $\frac{2}{k^2}-\frac{1}{k^3}$ by any number smaller than $\frac{1}{k^2}$. We improve the upper bound to $\frac{1}{k^2}(1+o(1))$ as $k\to \mathrm{\infty }$. For the class of bipartite graphs, we show that the best constant is exactly $\frac{1}{k^2}$ for every $k$. The results extend to the rectilinear variant of the $k$-planar crossing number.