PathWidth and ThreeDimensional StraightLine Grid Drawings of GraphsDujmović, Vida and Morin, Pat and Wood, David R. (2002) PathWidth and ThreeDimensional StraightLine Grid Drawings of Graphs. In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 4253(Official URL: http://dx.doi.org/10.1007/3540361510_5). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_5
AbstractWe prove that every nvertex graph G with pathwidth pw(G) has a threedimensional straightline grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded pathwidth the volume is O(n), and it follows that for graphs with bounded treewidth, such as seriesparallel graphs, the volume is O(n log² n). No better bound than O(n²) was previously known for drawings of seriesparallel graphs. For planar graphs we obtain threedimensional drawings with O(n²) volume and O(\sqrt{n}) aspect ratio, whereas all previous constructions with O(n²) volume have \Theta(n) aspect ratio.
Actions (login required)
