Geodesic
Bounded-degree graphs have arbitrarily large geometric thickness
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The geometric thickness of a graph $G$ is the minimum integer $k$ such that there is a straight line drawing of $G$ with its edge set partitioned into $k$ plane subgraphs. Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004] asked whether every graph of bounded maximum degree has bounded geometric thickness. We answer this question in the negative, by proving that there exists $\Delta$-regular graphs with arbitrarily large geometric thickness. In particular, for all $\Delta\geq9$ and for all large $n$, there exists a $\Delta$-regular graph with geometric thickness at least $c\sqrt{\Delta}\,n^{1/2-4/\Delta-\epsilon}$. Analogous results concerning graph drawings with few edge slopes are also presented, thus solving open problems by Dujmović et al. [Really straight graph drawings. In Proc. 12th International Symp. on Graph Drawing (GD '04), vol. 3383 of Lecture Notes in Comput. Sci., Springer, 2004] and Ambrus et al. [The slope parameter of graphs. Tech. Rep. MAT-2005-07, Department of Mathematics, Technical University of Denmark, 2005].
DOI : 10.37236/1029
Classification : 05C62, 05C10
Mots-clés : straight-line drawing of graphs, geometric graphs, geometric thickness, slope number 
@article{10_37236_1029,
     author = {J\'anos Bar\'at and Ji\v{r}{\'\i} Matou\v{s}ek and David R. Wood},
     title = {Bounded-degree graphs have arbitrarily large geometric thickness},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1029},
     zbl = {1080.05063},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1029/}
}
TY  - JOUR
AU  - János Barát
AU  - Jiří Matoušek
AU  - David R. Wood
TI  - Bounded-degree graphs have arbitrarily large geometric thickness
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1029/
DO  - 10.37236/1029
ID  - 10_37236_1029
ER  - 
%0 Journal Article
%A János Barát
%A Jiří Matoušek
%A David R. Wood
%T Bounded-degree graphs have arbitrarily large geometric thickness
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1029/
%R 10.37236/1029
%F 10_37236_1029
János Barát; Jiří Matoušek; David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1029

Cité par Sources :