The crossing number of a projective graph is quadratic in theface--width (Extended abstract)
Petr Hliněný, Gelasio Salazar, Isidoro Gitler, Jesús Leaños · Electronic Notes in Discrete Mathematics · 2007
We show that for each integer $g\geq0$ there is a constant $c>0$ such that every graph that embeds in the projective plane with sufficiently large face--width $r$ has crossing number at least $c.r^2$ in the orientable surface 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.