IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC