IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC