Next: Problem 52: QueueNumber of
Up: The Open Problems Project
Previous: Problem 50: Pointed Spanning
Problem 51: LinearVolume 3D Grid Drawings of Planar Graphs
 Statement
 Does every nvertex 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 noncrossing. The volume is of the
bounding box.
 Origin
 Felsner, Liotta, and Wismath [FLW02].
 Status/Conjectures
 Open.
 Partial and Related Results
 [FLW02]: Every nvertex outerplanar graph has a 3D
grid drawing with O(n) volume.
 [DW03b]: Every nvertex graph with bounded treewidth
has a 3D grid drawing with O(n) volume.
 [DW04]: Every nvertex planar graph has a 3D grid
drawing with
O(n^{3/2}) volume.
 [Woo02]: Every nvertex planar graph has an
O(1)×O(1)×O(n) grid drawing
if and only if planar graphs have O(1) queuenumber.
(See Problem 52 for a definition of queuenumber.)
 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.
 DW04

Vida Dujmović and David R. Wood.
Threedimensional grid drawings with subquadratic
volume.
In János Pach, editor, Towards a Theory of Geometric
Graphs, volume 342 of Contemporary Mathematics, pages 5566. American
Mathematical Society, 2004.
 DW03b

Vida Dujmović and David R. Wood.
Treepartitions of ktrees 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 205217. SpringerVerlag, 2003.
 FLW02

Stefan Felsner, Giussepe Liotta, and Stephen Wismath.
Straightline 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 328342. Springer, 2002.
 Woo02

David R. Wood.
Queue layouts, treewidth, and threedimensional
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 348359.
Springer, 2002.
Next: Problem 52: QueueNumber of
Up: The Open Problems Project
Previous: Problem 50: Pointed Spanning
The Open Problems Project  December 04, 2015