HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER and Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width (Extended abstract). Electronic Notes in Discrete Mathematics. Elsevier, 2007, vol. 29, C, p. 219-223. ISSN 1571-0653. |
Other formats:
BibTeX
LaTeX
RIS
@article{722629, author = {Hliněný, Petr and Salazar, Gelasio and Gitler, Isidoro and Leanos, Jesus}, article_number = {C}, keywords = {crossing number; projective plane; face-width; grid}, language = {eng}, issn = {1571-0653}, journal = {Electronic Notes in Discrete Mathematics}, title = {The crossing number of a projective graph is quadratic in the face--width (Extended abstract)}, url = {http://www.congreso.us.es/eurocomb07/}, volume = {29}, year = {2007} }
TY - JOUR ID - 722629 AU - Hliněný, Petr - Salazar, Gelasio - Gitler, Isidoro - Leanos, Jesus PY - 2007 TI - The crossing number of a projective graph is quadratic in the face--width (Extended abstract) JF - Electronic Notes in Discrete Mathematics VL - 29 IS - C SP - 219-223 EP - 219-223 PB - Elsevier SN - 15710653 KW - crossing number KW - projective plane KW - face-width KW - grid UR - http://www.congreso.us.es/eurocomb07/ N2 - 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. ER -
HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER and Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width (Extended abstract). \textit{Electronic Notes in Discrete Mathematics}. Elsevier, 2007, vol.~29, C, p.~219-223. ISSN~1571-0653.
|