Problem 51: Linear-Volume 3D Grid Drawings of Planar Graphs

Statement

Does every n-vertex planar graph have a 3D grid drawing with O(n) volume? A 3D grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates such that the straight line segments representing the edges are pairwise non-crossing. The volume is of the bounding box.

Origin

Felsner, Liotta, and Wismath [FLW02].

Status/Conjectures

Open.

Partial and Related Results

1. [FLW02]: Every n-vertex outerplanar graph has a 3D grid drawing with O(n) volume.
2. [DW03b]: Every n-vertex graph with bounded treewidth has a 3D grid drawing with O(n) volume.
3. [DW04]: Every n-vertex planar graph has a 3D grid drawing with O(n^3/2) volume.
4. [Woo02]: Every n-vertex planar graph has an O(1)×O(1)×O(n) grid drawing if and only if planar graphs have O(1) queue-number. (See Problem 52 for a definition of queue-number.)

Related Open Problems

Problem 52.

Appearances

Above references.

Categories

graph drawing

Entry Revision History

D. Wood, 6 Dec. 2003; J. O'Rourke, 16 Mar. 2004.

Bibliography

DW04

Vida Dujmović and David R. Wood.
Three-dimensional grid drawings with sub-quadratic volume.
In János Pach, editor, Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics, pages 55-66. American Mathematical Society, 2004.

DW03b

Vida Dujmović and David R. Wood.
Tree-partitions of k-trees with applications in graph layout.
In Hans Bodlaender, editor, Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science (WG'03), volume 2880 of Lecture Notes in Comput. Sci., pages 205-217. Springer-Verlag, 2003.

FLW02

Stefan Felsner, Giussepe Liotta, and Stephen Wismath.
Straight-line drawings on restricted integer grids in two and three dimensions.
In Petra Mutzel, Michael Jünger, and Sebastian Leipert, editors, Proc. 9th International Symp. on Graph Drawing (GD '01), volume 2265 of Lecture Notes in Comput. Sci., pages 328-342. Springer, 2002.

Woo02

David R. Wood.
Queue layouts, tree-width, and three-dimensional graph drawing.
In Manindra Agrawal and Anil Seth, editors, Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FST TCS '02), volume 2556 of Lecture Notes in Comput. Sci., pages 348-359. Springer, 2002.