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

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr GITLER Isidoro SALAZAR Gelasio LEANOS Jesus

Year of publication 2007
Type Conference abstract
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.