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

•  
• Overview
•  
• Research
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

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 cg r2 in the orientable surface Σ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. © 2007 Elsevier B.V. All rights reserved.

authors

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

publication date

• 2007-01-01

published in

• Electronic Notes in Discrete Mathematics  Journal

Research

keywords

• approximation; crossing number; face-width; projective graph

Identity

Digital Object Identifier (DOI)

• 10.1016/j.endm.2007.07.037

Additional Document Info

start page

• 219

end page

• 223

volume

• 29

issue

• SPEC. ISS.