Abstract
The nothreeinline problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. In 1951, Erdös proved that the answer is θ(n). We consider the analogous threedimensional problem, and prove that the maximum number of points in the n × n × n grid with no three collinear is θ(n ^{2}). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint in ℤ^{3}, such that the linesegment representing each edge does not intersect any vertex, except for its own endpoints. Note that edges may cross. A 3D drawing of a complete graph K_{n} is nothing more than a set of n gridpoints with no three collinear. A slight generalisation of our first result is that the minimum volume for a 3D drawing of K_{n} is θ(n ^{3/2}). This compares favourably to θ(n^{3}) when edges are not allowed to cross. Generalising the construction for K^{n}, we prove that every kcolourable graph on n vertices has a 3D drawing with O(n√k) volume. For the kpartite Turán graph, we prove a lower bound of Ω((kn)^{3/4}).
Original language  English 

Title of host publication  Graph Drawing 
Subtitle of host publication  12th International Symposium, GD 2004 New York, NY, USA, September 29October 2, 2004 Revised Selected Papers 
Editors  János Pach 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  395402 
Number of pages  8 
ISBN (Print)  3540245286 
DOIs  
Publication status  Published  1 Dec 2004 
Externally published  Yes 
Event  Graph Drawing 2004  New York, United States of America Duration: 29 Sept 2004 → 2 Oct 2004 Conference number: 12th https://link.springer.com/book/10.1007/b105810 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  3383 
ISSN (Print)  03029743 
Conference
Conference  Graph Drawing 2004 

Abbreviated title  GD 2004 
Country/Territory  United States of America 
City  New York 
Period  29/09/04 → 2/10/04 
Internet address 
