The crossing number of a projective graph is quadratic in the face-width
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Conference abstract |
| MU Faculty or unit | |
| Citation | |
| Description | We show that for each nonnegative integer $g$ there is a constant $\constc > 0$ such that every graph that embeds in the projective plane with face--width at least $r$ has crossing number at least $\constc r^2$ in the orientable surface 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: |