Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs

We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n), and it follows that for graphs with bounded tree-width, such as series-parallel graphs, the volume is O(n log² n). No better bound than O(n²) was previously known for drawings of series-parallel graphs. For planar graphs we obtain three-dimensional drawings with O(n²) volume and O(\sqrt{n}) aspect ratio, whereas all previous constructions with O(n²) volume have \Theta(n) aspect ratio