Computing Upward Planar Drawings Using Switch-Regularity Heuristics

Let G be an upward planar embedded digraph. The classical approach used to compute an upward drawing of G consists of two steps: (i) A planar st-digraph including G is constructed adding a suitable set of dummy edges; (ii) A polyline drawing of the st-digraph is computed using standard techniques, and dummy edges are then removed. For computational reasons, the number of dummy edges added in the first step should be kept as small as possible. However, as far as we know, there is only one algorithm known in the literature to compute an st-digraph including an upward planar embedded digraph. In this paper we describe an alternative heuristic, which is based on the concept of switch-regularity introduced by Di Battista and Liotta (1998). We experimentally prove that the new heuristic significantly reduces the number of dummy edges added to determine the including st-digraph. For digraphs with low density, such a reduction has a positive impact on the quality of the final drawing and on the overall running time required by the drawing process.