The crossing number cr(G) of a graph G is the minimum number of crossings over all possible drawings of G in the plane. Analogously, the k-planar crossing number of G, denoted by cr_{k edges of G in k disjoint planes. We present new bounds on the k-planar crossing number of complete graphs and complete bipartite graphs. In particular, for the case of k=2, we improve the current best lower bounds on biplanar crossing numbers by a factor of 1.37 for complete graphs, and by a factor of 1.34 for complete bipartite graphs. We extend our results to the k-planar crossing number of complete (bipartite ) graphs, for any positive integer k \geq 2. To better understand the relation between crossing numbers and biplanar crossing numbers, we pose a new problem of finding the largest crossing number that implies biplanarity. In particular, we prove that for every graph G, cr(G) \leq 10 implies cr_{2
The biplanar crossing number of a graph G is the minimum number of crossings over all possible drawings of the edges of G in two disjoint planes. We present new bounds on the biplanar crossing number of complete graphs and complete bipartite graphs. In particular, we prove that the biplanar crossing number of complete bipartite graphs can be approximated to within a factor of 3, improving over the best previously known approximation factor of 4.03. For complete graphs, we provide a new approximation factor of 3.17, improving over the best previous factor of 4.34. We provide similar improved approximation factors for the k-planar crossing number of complete graphs and complete bipartite graphs, for any positive integer k . We also investigate the relation between (ordinary) crossing number and biplanar crossing number of general graphs in more depth, and prove that any graph with a crossing number of at most 10 is biplanar.
R
crossing number cr(G)
biplanar crossing number
R
G in the plane. Analogously, the k-planar crossing number of G, denoted by cr_{k
the
R
k
two
R
k-planar
biplanar
R
for the case of k=2, we improve the current best lower bounds on biplanar crossing numbers by
we prove that the biplanar crossing number of complete bipartite graphs can be approximated to within
R
1.37 for
3, improving over the best previously known approximation factor of 4.03. For
R
and by a factor of 1.34 for complete bipartite graphs. We extend our results to
we provide a new approximation factor of 3.17, improving over the best previous factor of 4.34. We provide similar improved approximation factors for
R
(bipartite )
graphs and complete bipartite
R
\geq 2. To better understand
. We also investigate
R
crossing numbers
(ordinary) crossing number
R
numbers, we pose a new problem of finding the largest crossing number that implies biplanarity. In particular, we prove that for every graph G, cr(G) \leq
number of general graphs in more depth, and prove that any graph with a crossing number of at most
R
implies cr_{2
is biplanar.