2016/08/30 by Emilio Di Giacomo, Giuseppe Liotta, Di Giacomo, Emilio +3 · 1 citation
Computer Science · #Cellular Automata and Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1608.08425
openalex publication_date 2016/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is proved that every series-parallel digraph whose maximum vertex-degree is Δ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. This is shown to be worst-case optimal in terms of the number of slopes. Furthermore, our construction gives rise to drawings with optimal angular resolution \fracπΔ. A variant of the proof technique is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) one-bend planar drawing with \lceil\fracΔ2\rceil distinct slopes if biconnected, and with \lceil\fracΔ2\rceil+1 distinct slopes if connected.