The crossing number of a projective graph is quadratic in the face--width (Extended abstract)
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Notes in Discrete Mathematics |
| MU Faculty or unit | |
| Citation | |
| Web | |
| Field | General mathematics |
| Keywords | crossing number; projective plane; face-width; grid |
| Description | We show that for each integer $g\geq0$ there is a constant $c>0$ such that every graph that embeds in the projective plane with sufficiently large face--width $r$ has crossing number at least $c.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: |