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 [Formula presented]. 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 [Formula presented] distinct slopes if biconnected, and with [Formula presented] distinct slopes if connected.
1-bend upward planar slope number of SP-digraphs
Di Giacomo E.;Liotta G.;Montecchiani F.
2020
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 [Formula presented]. 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 [Formula presented] distinct slopes if biconnected, and with [Formula presented] distinct slopes if connected.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
