The Crossing Number of a Projective Graph is Quadratic in the Face–Width

Abstract

We show that for each integer $g\geq0$ there is a constant $c_g > 0$ such that every graph that embeds in the projective plane with sufficiently large face–width $r$ has crossing number at least $c_g r^2$ in the orientable surface $\Sigma_g$ of genus $g$. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree.