Geodesic
Crossing Numbers and Cutwidths
Journal of Graph Algorithms and Applications, Tome 7 (2003) no. 3, pp. 245-251.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The crossing number of a graph G=(V,E), denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Wee assume that the drawing is good, i.e., incident edges do not cross, two edges cross at most once and at most two edges cross in a point of the plane. Leighton [] proved that for any n-vertex graph G of bounded degree, its crossing number satisfies cr(G)+n=Ω(bw2(G)), where bw(G) is the bisection width of G. The lower bound method was extended for graphs of arbitrary vertex degrees to cr(G)+[1/16] ∑v ∈ Gdv2 = Ω(bw2(G)) in [,], where dv is the degree of any vertex v. We improve this bound by showing that the bisection width can be replaced by a larger parameter - the cutwidth of the graph. Our result also yields an upper bound for the path-width of G in terms of its crossing number. 
@article{JGAA_2003_7_3_a0,
     author = {Hristo Djidjev and Imrich Vr\v{t}o},
     title = {Crossing {Numbers} and {Cutwidths}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {245--251},
     publisher = {mathdoc},
     volume = {7},
     number = {3},
     year = {2003},
     doi = {10.7155/jgaa.00069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00069/}
}
TY  - JOUR
AU  - Hristo Djidjev
AU  - Imrich Vrťo
TI  - Crossing Numbers and Cutwidths
JO  - Journal of Graph Algorithms and Applications
PY  - 2003
SP  - 245
EP  - 251
VL  - 7
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00069/
DO  - 10.7155/jgaa.00069
LA  - en
ID  - JGAA_2003_7_3_a0
ER  - 
%0 Journal Article
%A Hristo Djidjev
%A Imrich Vrťo
%T Crossing Numbers and Cutwidths
%J Journal of Graph Algorithms and Applications
%D 2003
%P 245-251
%V 7
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00069/
%R 10.7155/jgaa.00069
%G en
%F JGAA_2003_7_3_a0
Hristo Djidjev; Imrich Vrťo. Crossing Numbers and Cutwidths. Journal of Graph Algorithms and Applications, Tome 7 (2003) no. 3, pp. 245-251. doi : 10.7155/jgaa.00069. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00069/

Cité par Sources :