Geodesic
The crossing number of a projective graph is quadratic in the face-width
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
We show that for each integer $g\geq0$ there is a constant $c_g > 0$ such that every graph that embeds in the projective plane with sufficiently large face–width $r$ has crossing number at least $c_g r^2$ in the orientable surface $\Sigma_g$ 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.
DOI : 10.37236/770
Classification : 05C10, 05C62, 05C85, 68R10
Mots-clés : graph embedding, projective plane, face-width, crossing number, orientable surface, genus, projective graphs, approximantion algorithm 
I. Gitler; P. Hliněný; J. Leaños; G. Salazar. The crossing number of a projective graph is quadratic in the face-width. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/770
@article{10_37236_770,
     author = {I. Gitler and P. Hlin\v{e}n\'y and J. Lea\~nos and G. Salazar},
     title = {The crossing number of a projective graph is quadratic in the face-width},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/770},
     zbl = {1159.05016},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/770/}
}
TY  - JOUR
AU  - I. Gitler
AU  - P. Hliněný
AU  - J. Leaños
AU  - G. Salazar
TI  - The crossing number of a projective graph is quadratic in the face-width
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/770/
DO  - 10.37236/770
ID  - 10_37236_770
ER  - 
%0 Journal Article
%A I. Gitler
%A P. Hliněný
%A J. Leaños
%A G. Salazar
%T The crossing number of a projective graph is quadratic in the face-width
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/770/
%R 10.37236/770
%F 10_37236_770

Cité par Sources :