abstract

• We show that for each integer g ≥ 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 cgr 2 in the orientable surface Σ3 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.

authors

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

publication date

• 2008-01-01

published in

• Electronic Journal of Combinatorics  Journal

start page

end page

volume

• 15

issue

• 1 R