2018/03/27 by Michael A. Bekos, Emilio Di Giacomo, Bekos, Michael A. +7 · 1 citation
Computer Science · Engineering · Environmental Science · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.1803.09949
openalex publication_date 2018/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that every set \mathcal 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 \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.