Three-Dimensional Grid Drawings of Graphs

A three-dimensional grid drawing of a graph G is a placement of the vertices at distinct integer points so that the straight-line segments representing the edges of G are pairwise non-crossing. It is shown that for any fixed r 2, every r-colorable graph of n vertices has a three-dimensional grid drawing that fits into a box of volume O(n 2 ). The order of magnitude of this bound cannot be improved