Geodesic
Bounded-degree graphs have arbitrarily large geometric thickness
The electronic journal of combinatorics, Tome 13 (2006)

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

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

Cité par Sources :