## DIMACS TR: 97-73

## Three-dimensional Grid Drawings of Graphs

### Authors: János Pach, Torsten Thiele and Géza Tóth

**
ABSTRACT
**

A three-dimensional {\em 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\geq
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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-73.ps.gz

DIMACS Home Page