| HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width. Electronic Journal of Combinatorics. internet: -, 2008, roč. 15, č. 1, s. R46, 8 s. ISSN 1077-8926. |
Další formáty:
BibTeX
LaTeX
RIS
@article{764730,
author = {Hliněný, Petr and Salazar, Gelasio and Gitler, Isidoro and Leanos, Jesus},
article_location = {internet},
article_number = {1},
keywords = {crossing number; projective plane; face-width},
language = {eng},
issn = {1077-8926},
journal = {Electronic Journal of Combinatorics},
title = {The crossing number of a projective graph is quadratic in the face--width},
url = {http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf},
volume = {15},
year = {2008}
}
TY - JOUR
ID - 764730
AU - Hliněný, Petr - Salazar, Gelasio - Gitler, Isidoro - Leanos, Jesus
PY - 2008
TI - The crossing number of a projective graph is quadratic in the face--width
JF - Electronic Journal of Combinatorics
VL - 15
IS - 1
SP - R46
EP - R46
PB - -
SN - 10778926
KW - crossing number
KW - projective plane
KW - face-width
UR - http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf
N2 - 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.
ER -
HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width. \textit{Electronic Journal of Combinatorics}. internet: -, 2008, roč.~15, č.~1, s.~R46, 8 s. ISSN~1077-8926.
|
