**Next:** Problem 52: Queue-Number of Planar Graphs

**Previous:** Problem 50: Pointed Spanning Trees in Triangulations

- 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
[FLW02]: Every n-vertex outerplanar graph has a 3D grid drawing with O(n) volume.

[DW03b]: Every n-vertex graph with bounded treewidth has a 3D grid drawing with O(n) volume.

[DW04]: Every n-vertex planar graph has a 3D grid drawing with O(n^{3/2}) volume.

[Woo02]: Every n-vertex planar graph has an O(1) \times O(1) \times 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
- Appearances
Above references.

- Categories
graph drawing

- Entry Revision History
D. Wood, 6 Dec. 2003; J. O’Rourke, 16 Mar. 2004.

- [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.