Další formáty:
BibTeX
LaTeX
RIS
@proceedings{755896,
author = {Hliněný, Petr and Gitler, Isidoro and Salazar, Gelasio and Leanos, Jesus},
booktitle = {Czech-Slovak Conference on Graph Theory 2007, Hradec nad Moravicí},
keywords = {crossing number; projective plane},
language = {eng},
isbn = {978-80-248-1445-2},
title = {The crossing number of a projective graph is quadratic in the face-width},
url = {http://graphs.vsb.cz/grafy2007},
year = {2007}
}
TY - CONF
ID - 755896
AU - Hliněný, Petr - Gitler, Isidoro - Salazar, Gelasio - Leanos, Jesus
PY - 2007
TI - The crossing number of a projective graph is quadratic in the face-width
SN - 9788024814452
KW - crossing number
KW - projective plane
UR - http://graphs.vsb.cz/grafy2007
N2 - We show that for each nonnegative integer $g$ there is a constant $\constc > 0$ such that every graph that embeds in the projective plane with face--width at least $r$ has crossing number at least $\constc 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, Isidoro GITLER, Gelasio SALAZAR a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face-width. In \textit{Czech-Slovak Conference on Graph Theory 2007, Hradec nad Moravicí}. 2007. ISBN~978-80-248-1445-2.
|
