1. Volume requirements of 3D upward drawings
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, Meijer, Henk, and Wismath, Stephen K.
- Subjects
- *
HASSE diagrams , *DIRECTED graphs , *MATHEMATICAL analysis , *TREE graphs , *CHARTS, diagrams, etc. , *GRAPH theory , *DIMENSIONS - Abstract
Abstract: This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed acyclic graphs whose volume requirement is super-linear. We also prove that for the case of directed trees a linear-volume upper bound is achievable. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF