IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

$k$-planar crossing numbers

  • Sept. 19, 2014
  • 2:30 p.m.
  • LeConte 312

Abstract

The $k$-planar crossing number $cr _ k(G)$ of a graph $G$ is $\min _ {G _ 1\cup G _ 2\cup \cdots \cup G _ k=G} \{cr(G _ 1)+cr(G _ 2)+\ldots + cr(G _ k)\}$, where $cr$ is the planar crossing number. We give near tight upper bounds for $cr _ k(G)$ in terms of a constant multiple of $cr(G)$. This is a joint work with J\'anos Pach, Csaba T\'oth and G\'eza T\'oth.

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