Gitler, I.; Hlineny, P.; Leaños, J.; Salazar, G.

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

Electron. J. Comb. 15(1), Research Paper R46, 8 p. (2008)


Summary: We show that for each integer g $\geq 0$ there is a constant cg > 0 such that every graph that embeds in the projective plane with sufficiently large face-width r has crossing number at least 2 cgr 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.

Mathematics Subject Classification

05C10, 05C62, 05C85