| 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.
|
