1. 1-bend upward planar slope number of SP-digraphs.
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Subjects
- *
DRAWING , *ALGORITHMS , *EDGES (Geometry) , *CONSTRUCTION - Abstract
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. The construction is worst-case optimal in terms of the number of slopes, and it gives rise to drawings with optimal angular resolution π Δ. A variant of the drawing algorithm is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) 1-bend planar drawing with ⌈ Δ 2 ⌉ distinct slopes if biconnected, and with ⌈ Δ 2 ⌉ + 1 distinct slopes if connected. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF