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

Warning

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

Authors	HLINĚNÝ Petr SALAZAR Gelasio GITLER Isidoro LEANOS Jesus
Year of publication	2008
Type	Article in Periodical
Magazine / Source	Electronic Journal of Combinatorics
MU Faculty or unit	Faculty of Informatics
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:	Highly Parallel and Distributed Computing Systems Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity