## Using block designs in crossing number bounds

- Aug. 31, 2018
- 2:30 p.m.
- LeConte 317R

## Abstract

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\ge 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)+\ldots+\mathrm{Cr}(G _ {k})$ over all graphs $G _ 1, G _ 2,\ldots,
G _ {k}$ with $\cup _ {i=1}^{k}G _ i=G$.
Pach et al. [*Computational Geometry: Theory and Applications*
**68** 2--6, (2018)] showed that for every $k\ge 1$, we have $\mathrm{Cr} _ k(G)\le
\left(\frac{2}{k2}-\frac1{k3}\right)\mathrm{Cr}(G)$ and that this bound does not remain
true if we replace the constant $\frac{2}{k2}-\frac1{k3}$ by any number
smaller than $\frac1{k2}$. We improve the upper bound to $\frac{1}{k2}(1+o(1))$ as
$k\rightarrow \infty$. For the class of bipartite graphs, we show that
the best constant is exactly $\frac{1}{k2}$ for every $k$.
The results extend to the rectilinear variant of the $k$-planar crossing number.

This is joint work with John Asplund, Éva Czabarka, Gregory Clark, Garner Cochran, Arran Hamm, Gwen Spencer, Libby Taylor and Zhiyu Wang originating from a Mathematics Research Communities program.