Three-dimensional grid drawings with sub-quadratic volume
Vida Dujmović, David R. Wood · Contemporary mathematics - American Mathematical Society · 2004
A three-dimensional 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. A O(n 3/2 ) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n 2 ). These results (partially) solve open problems due to Pach, Thiele, and T6th [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].