Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method
Éva Czabarka, Ondřej Sýkora, Łászló A. Székely, Imrich Vrt’o · Random Structures and Algorithms · 2008
Abstract 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. We show that cr 2 ( G ) ≤ (3/8) cr ( G ). Using this result recursively, we bound the thickness by Θ( G ) ‐ 2 ≤ Kcr 2 ( G ) 0.4057 log 2 n 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. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008