The crossing number of a projective graph is quadratic in the face-width (Q1010759)

Summary: We show that for each integer \(g\geq 0\) 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.