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

  • I. Gitler
  • P. Hliněný
  • J. Leaños
  • G. Salazar


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.

Article Number