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