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) 2 ·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 2 n). No better bound than O(n 2) was previously known for drawings of series-parallel graphs. For planar graphs we obtain three-dimensional drawings with O(n 2) volume and O(√n) aspect ratio, whereas all previous constructions with O(n 2) volume have θ(n) aspect ratio.
|Organisation||School of Computer Science|
Dujmović, V, Morin, P, & Wood, D. (2002). Path-width and three-dimensional straight-line grid drawings of graphs.