Geodesic
The crossing number of a projective graph is quadratic in the face-width
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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

Cité par Sources :