## Biplanar crossing numbers II: comparing crossing numbers and biplanar crossing numbers using the probabilistic method

**A 2006 Preprint by
É. Czabarka,
O. Sykora,
L. Székely, and
I. Vrto
**

- 2006:04
The biplanar crossing number $cr _ 2(G)$ of a graph

*G*is $\min\{cr(G _ 1)+cr(G _ 2)\}$, where*cr*is the planar crossing number and $G _ 1\cup{G _ 2}=G$. We show that $cr _ 2(G)\leq(\frac{3}{8})cr(G)$. Using this result recursively, we bound the thickness by $\Theta(G)-2\leq$ ${Kcr _ 2}(G)^{0.4507}\log _ 2n$ with some constant*K.*A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph*G*of this size, which simultaneously has the following properties: $cr(G)$ is roughly as large as it can be for any graph of that size, and $cr _ 2(G)$ is as small as it can be for any graph of that size. The existence is shown using the probabilistic method.