Universal Slope Sets for Upward Planar Drawings
Michael A. Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani · Algorithmica · 2022
Abstract 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 $$\mathcal {S}$$ S of $$\varDelta $$ Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree $$\varDelta $$ Δ , i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in $$\mathcal {S}$$ S . This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of $$\mathcal {S}$$ S , it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set $$\mathcal {S}$$ S can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most $$4n-9$$ 4 n - 9 bends in total.