Drawing compound digraphs and its application to an idea organizer (abstract)

An upward drawing of an acyclic digraph is a planar straight-line drawing with the additional requirement that all the edges flow in the same direction, e.g., from bottom to top. The literature on the problem of constructing upward drawings of important classes of digraphs is surveyed. First, it is show that there is a family of binary trees with n vertices requiring Ω( n log n ) area for any upward drawing; moreover, that bound is tight, i.e. each binary tree with n vertices can be drawn with O ( n log n ) area. Second, motivated by the elegant H -tree layout algorithm for constructing non-upward drawings of complete binary trees, an algorithm is presented for constructing an upward drawing of a complete binary tree with n vertices in O(n) area. This result is extended to the drawings of Fibonacci trees . Third, it is shown that the area requirement of upward drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, parallel and sequential drawing algorithms are presented that are optimal with respect to both the time complexity and to the area achieved. Several results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.