The crossing number of a projective graph is quadratic in the face--width
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Journal of Combinatorics |
| MU Faculty or unit | |
| Citation | |
| Web | online paper |
| Field | General mathematics |
| Keywords | crossing number; projective plane; face-width |
| Description | We show that for each integer g there is a constant Cg 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 Sg 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. |
| Related projects: |