Universal Slope Sets for Upward Planar Drawings

We study universal sets of slopes for computing upward planar drawings of planar st-graphs. We first consider a subfamily of planar st-graphs, called bitonic st-graphs. We prove that every set S of Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree Δ, i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in S. This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of S, it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set S can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most 4 n- 9 bends in total.