Using block designs in crossing number bounds. (English) Zbl 1427.05060
Summary: The crossing number \(\mathrm{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\geq 1\), the \(k\)-planar crossing number of \(G\), \(\mathrm{CR}_k(G)\), is defined as the minimum of \(\mathrm{CR}(G_1) + \mathrm{CR}(G_2) + \cdots + \mathrm{CR}(G_k)\) over all graphs \(G_1, G_2, \dots, G_k\) with \(\cup_{i=1}^k G_i=G\). J. Pach et al. [Comput. Geom. 68, 2–6 (2018; Zbl 1380.05165)] showed that for every \(k\ge1\), we have \(\mathrm{CR}_k(G) \leq (2/k^2 - 1/k^3)\mathrm{CR}(G)\) and that this bound does not remain true if we replace the constant \(2/k^2 - 1/k^3\) by any number smaller than \(1/k^2\). We improve the upper bound to \((1/k^2)(1+o(1))\) as \(k\rightarrow\infty\). For the class of bipartite graphs, we show that the best constant is exactly \(1/k^2\) for every \(k\). The results extend to the rectilinear variant of the \(k\)-planar crossing number.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05B05 | Combinatorial aspects of block designs |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
