next up previous
Next: Problem 52: Queue-Number of Up: The Open Problems Project Previous: Problem 50: Pointed Spanning


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(n3/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.


next up previous
Next: Problem 52: Queue-Number of Up: The Open Problems Project Previous: Problem 50: Pointed Spanning
The Open Problems Project - December 04, 2015