Note on k-planar crossing numbers

Abstract

The crossing number $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$-planar crossing number of $G$, $c{r}_k(G)$, is defined as the minimum of $cr(G_0)+cr(G_1)+\dots +cr(G_{k-1})$ over all graphs $G_0,G_1,\dots ,G_{k-1}$ with ${\cup }_{i=0}^{k-1}{G}_i=G$. It is shown that for every $k\ge 1$, we have $c{r}_k(G)\le \left(\frac{2}{k^2}-\frac{1}{k^3}\right)cr(G)$. 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}$. Some of the results extend to the rectilinear variants of the $k$-planar crossing number.

References in corpus (1)

• Geometric Biplane Graphs I: Maximal Graphs

Cited by in corpus (5)

• Using Block Designs in Crossing Number Bounds
• New Bounds on the Biplanar and $k$-Planar Crossing Numbers
• Some remarks on the midrange crossing constant
• Midrange crossing constants for graphs classes
• Approximating the rectilinear crossing number