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

Dujmović, Vida and Morin, Pat and Wood, David R. (2002) Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 42-53(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_5
Classifications: P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D

Actions (login required)

View Item View Item