HLINĚNÝ, Petr, Gelasio SALAZAR, Isidoro GITLER and Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width. Electronic Journal of Combinatorics. internet: -, 2008, vol. 15, No 1, p. R46, 8 pp. ISSN 1077-8926. |
Other formats:
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 and Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width. \textit{Electronic Journal of Combinatorics}. internet: -, 2008, vol.~15, No~1, p.~R46, 8 pp. ISSN~1077-8926.
|