Grid-drawings of graphs in three-dimensions

Abstract

Using probabilistic methods, we obtain grid-drawings of graphs without crossings with low volume and small aspect ratio. We show that every $D$-degenerate graph on $n$ vertices can be drawn in $[m{]}^3$ where $m^3=O(D^{2}n\log n)$. In particular, every graph of bounded maximum degree can be drawn in a grid with volume $O(n\log n)$.