1-Bend Upward Planar Drawings of SP-Digraphs

Di Giacomo, Emilio and Liotta, Giuseppe and Montecchiani, Fabrizio (2016) 1-Bend Upward Planar Drawings of SP-Digraphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 123-130(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_10).

Full text not available from this repository.


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 π/Δ . 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 ⌈Δ/2⌉ distinct slopes if biconnected, and with ⌈Δ/2⌉+1 distinct slopes if connected.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1537

Actions (login required)

View Item View Item