Volume requirements of 3D upward drawings (Q1011762)

The authors study \textit{upward 3D drawing} of directed acyclic graphs which is realization of the embedding of such graphs into the simple cubic lattice so that the edges are straight-line segments and are oriented in a common direction. They show that there exists a family of outerplanar directed acyclic graphs which require \(\Omega (n^{1.5})\) volume. It is also shown that directed trees admit linear volume, that is, they can be drawn on a grid of size \(O(1) \times O(1) \times O(n)\).