
460 CHAPTER 14. THREE-DIMENSIONAL DRAWINGS
also been made for more general class e s of graphs. In particular, all proper minor-closed
families of graphs have been proved to admit O(n
3
2
) volume 3D grid drawings [DW04c].
Refer to Table 14.1 for exact bounds.
Most, if not all, of the successful attempts to deri ve linear volume bounds have been done
by constructing 3D grid drawings that fit in a bounding box with di men si ons O(1)×O(1) ×
O(n). In such a drawing all the vertices li e on O(1) parallel lines. Thus not only does
such a drawing have many quadruples of vertices that are copl anar , but in fact a constant
fraction of all vertices are collinear. ...