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.
publication date
published in
Research
keywords
-
approximation; crossing number; face-width; projective graph
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue