Bounded-degree graphs can have arbitrarily large slope numbers (Q2583679)

A straight-line or geometric drawing 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 slope number of \(G\) is the smallest number of distinct edge slopes used in a straight-line drawing of \(G\). The authors prove that, for any given integer \(d\geq 5\), there exists an \(n\)-vertex graph of maximum degree \(d\) whose slope number is at least \(n^{1/2-1/(d-2)-o(1)}\). In particular, bounded-degree graphs can have arbitrarily large slope number, solving an open problem posed by \textit{V. Dujmović, M. Suderman} and \textit{D. R. Wood} [Lect. Notes Comput. Sci. 3383, 122--132 (2005; Zbl 1111.68571)], and improving a result by \textit{J. Barát, J. Matoušek} and \textit{D. R. Wood} [Electron. J. Comb. 13, No. 1, Research paper R3 (2006; Zbl 1080.05063)].