Name
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 Ω(nlogn) area for any upward drawing; moreover, that bound is tight, i.e. each binary tree with n vertices can be drawn with O(n logn) 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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1145/152992.153000 | ACM SIGACT News |
Keywords | Field | DocType |
n vertex,binary tree,optimal area,naive drawing strategy,compound digraph,area requirement,complete binary tree,idea organizer,non-upward drawing,upward drawing,planar straight-line drawing,exponential area,series parallel,time complexity | Discrete mathematics,Combinatorics,Exponential function,Vertex (geometry),Planar embedding,Binary tree,Planar,Time complexity,Digraph,Mathematics,Fibonacci number | Journal |
Volume | Issue | Citations |
24 | 1 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kozo Sugiyama | 1 | 1011 | 142.82 |