Graph drawings with few slopes (Q2385698)

Let \(G\) be a graph. The minimum number of distinct edge slopes in a drawing of \(G\) is called the \textit{slope-number} and it is denoted by \(sn(G)\). Some upper and lower bounds on \(sn(G)\) and \(csn(G)\) (convex case) are obtained in this paper. Theorem 1 says that for all \(\triangle \geq 5\) and \(\varepsilon >0\), for all sufficiently large \(n\), there exists a \(\triangle\)-regular \(n\)-vertex graph \(G\) with slope-number \(sn(G)>n^{1-(8+\varepsilon)/(\triangle+4)}\) (bounded degree and unbounded slope-number). Giving partial solution to the problem of estimating \(sn(G)\) for a complete multipartite graph \(G\), it is proved that \(sn(G)\leq csn(G)=\triangle(G)\) when \(G\) is a complete \(k\)-partite graph and \(k-1\) is a power of two. The article shows that a class of graphs with a particular structure have a drawing with at most \(k+s+s\ell(k^2-k)\) distinct slopes, where \(\ell\) is the number of distinct edge lengths. Two more results obtained in the paper must be mentioned. (I) Let \(G\) be a graph with \(n\) vertices, maximum degree \(\triangle \geq 1\), and treewidth \(k\geq 1\). Then \(G\) has a drawing with \({\mathcal{O}}(k^3\triangle^4 \log(n))\) slopes. (II) Every graph \(G\) has a \(1\)-bend drawing with \(\triangle(G)+1\) slopes. The proof of (I) is based on the fact that every tree \(T\) with pathwidth \(k\), has a drawing with \(\triangle(T)-1\) slopes and \(2k-1\) distinct edge lengths.