Bounded-degree graphs have arbitrarily large geometric thickness (Q2583678)

A straight-line drawing or a geometric graph of a graph \(G\) is a layout of \(G\) in the plane such that the vertices are represented by distinct points, the edges are represented by (possibly crossing) line segments connecting the corresponding point pairs and not passing though any other point that represents a vertex. The geometric thickness of \(G\) is the minimum number of planar subgraphs \(D\) of a geometric graph \(G\) whose union is \(D\). The slope number of \(G\) is the smallest number of distinct edge slopes used in a straight-line drawing \(D\) of \(G\). The authors prove that, for all \(\Delta\geq 9\) and \(\varepsilon>0\), for all large \(n>n(\varepsilon)\) and \(n\geq c\Delta\), there exists a \(\Delta\)-regular \(n\)-vertex graph with geometric thickness at least \(c\sqrt{\Delta}n^{1/2-4/\Delta -\varepsilon}\), for some absolute constant \(c\). This solves an open problem posed by \textit{D.~Epptein} [Contemp. Math. 342, 75--86 (2004; Zbl 1067.05022)]. The authors also prove that, for all \(\Delta\geq 5\), there exists a \(\Delta\)-regular graph with arbitrarily large slope number, solving an open problem posed by \textit{V. Dujmović} et al. [Lect. Notes Comput. Sci. 3383, 122--132 (2005; Zbl 1111.68571)]. This result on the slope number of bounded-degree graphs has been improved by \textit{J.~Pach} and \textit{D.~Pálvölgyi} [Electron. J. Comb. 13, No. 1, Research paper N1 (2006; Zbl 1080.05064)]. They show that, for all \(\Delta\geq 5\), there exists a \(\Delta\)-regular \(n\)-vertex graph whose slope number is at least \(n^{1/2-1/(\Delta-2)-o(1)}\).