Universal Slope Sets for Upward Planar Drawings

Abstract

We prove that every set $\mathcal{S}$ of $\Delta$ slopes containing the horizontal slope is universal for $1$-bend upward planar drawings of bitonic $st$-graphs with maximum vertex degree $\Delta$, i.e., every such digraph admits a $1$-bend upward planar drawing whose edge segments use only slopes in $\mathcal{S}$. This result is worst-case optimal in terms of the number of slopes, and, for a suitable choice of $\mathcal{S}$, it gives rise to drawings with worst-case optimal angular resolution. In addition, we prove that every such set $\mathcal{S}$ can be used to construct $2$-bend upward planar drawings of $n$-vertex planar $st$-graphs with at most $4n-9$ bends in total. Our main tool is a constructive technique that runs in linear time.

Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)