
14.2. STRAIGHT-LINE AND POLYLINE GRID DRAWINGS 465
that utn(G
n
) ≥
√
2n. Theorem 14.5 implies that 2XY ≥ utn(G
n
) ≥
√
2n. Hence the
volume is Ω(n
3/2
) [DLMW05].
This result highlights a substantial difference between 3D grid drawings of undirected
graphs and upward 3D grid drawings of dags, since every (undirected) outerplanar graph
has a 3D grid drawing with linear volume [F LW01]. In th e full version of their paper, Di
Giacomo et a l. [DLMW05] constructed an upward 3D grid drawing of G
n
with O(n
3/2
)
volume. It is unknown whether every n-vertex outerplanar dag has an upward 3D grid
drawing with O(n
3/2
) volume.
The proof that every graph has a 3D grid drawing ...