Geodesic
Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions
The electronic journal of combinatorics, Tome 11 (2004) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We extend a lower bound due to Shahrokhi, Sýkora, Székely and Vrťo for the outerplanar crossing number (in other terminologies also called convex, circular and one-page book crossing number) to a more general setting. In this setting we can show a better lower bound for the outerplanar crossing number of hypercubes than the best lower bound for the planar crossing number. We exhibit further sequences of graphs, whose outerplanar crossing number exceeds by a factor of $\log n$ the planar crossing number of the graph. We study the circular arrangement problem, as a lower bound for the linear arrangement problem, in a general fashion. We obtain new lower bounds for the circular arrangement problem. All the results depend on establishing good isoperimetric functions for certain classes of graphs. For several graph families new near-tight isoperimetric functions are established.
DOI : 10.37236/1834
Classification : 05C10, 05C62
Mots-clés : edge forwarding index 
@article{10_37236_1834,
     author = {\'Eva Czabarka and Ondrej S\'ykora and L\'aszl\'o A. Sz\'ekely and Imrich Vr\v{t}o},
     title = {Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions},
     journal = {The electronic journal of combinatorics},
     year = {2004},
     volume = {11},
     number = {1},
     doi = {10.37236/1834},
     zbl = {1080.05022},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1834/}
}
TY  - JOUR
AU  - Éva Czabarka
AU  - Ondrej Sýkora
AU  - László A. Székely
AU  - Imrich Vrťo
TI  - Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions
JO  - The electronic journal of combinatorics
PY  - 2004
VL  - 11
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1834/
DO  - 10.37236/1834
ID  - 10_37236_1834
ER  - 
%0 Journal Article
%A Éva Czabarka
%A Ondrej Sýkora
%A László A. Székely
%A Imrich Vrťo
%T Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions
%J The electronic journal of combinatorics
%D 2004
%V 11
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1834/
%R 10.37236/1834
%F 10_37236_1834
Éva Czabarka; Ondrej Sýkora; László A. Székely; Imrich Vrťo. Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1834

Cité par Sources :