Graph drawings with few slopes

. This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most

O (l o g n)

. Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper (http://arxiv.org/abs/math/0606450), planar drawings of graphs with few slopes are also considered.

Review text

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.

Recommendations

Cites work

Cited in

(29)

Describes a project that uses

Uses Software

LatDraw

This page was built for publication: Graph drawings with few slopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2385698)