Upward Planar Drawings with Three and More Slopes

We study upward planar straight-line drawings that use only a constant number of slopes. In particular, we are interested in whether a given directed graph with maximum in- and outdegree at most $k$ admits such a drawing with $k$ slopes. We show that this is in general NP-hard to decide for outerplanar graphs ($k = 3$) and planar graphs ($k \ge 3$). On the positive side, for cactus graphs deciding and constructing a drawing can be done in polynomial time. Furthermore, we can determine the minimum number of slopes required for a given tree in linear time and compute the corresponding drawing efficiently.