Tech Report CS-90-10

Area Requirement and Symmetry Display of Planar-Upward Drawings

Giuseppe Di Battista, Roberto Tamassia and Ioannis G. Tollis

April 1990


In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g. from bottom to top. Our contribution is twofold. First, we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges then the obtained drawing has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.

(complete text in pdf)