
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].
straight-line drawing of graphs, Graph representations (geometric and intersection representations, etc.), geometric graphs, FOS: Mathematics, Mathematics - Combinatorics, geometric thickness, Combinatorics (math.CO), 05C62, Pure Mathematics, slope number, Planar graphs; geometric and topological aspects of graph theory
straight-line drawing of graphs, Graph representations (geometric and intersection representations, etc.), geometric graphs, FOS: Mathematics, Mathematics - Combinatorics, geometric thickness, Combinatorics (math.CO), 05C62, Pure Mathematics, slope number, Planar graphs; geometric and topological aspects of graph theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 27 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
