### Abstract

The no-three-in-line 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 three-dimensional 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 line-segment 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 k-colourable graph on n vertices has a 3D drawing with O(n√k) volume. For the k-partite Turán graph, we prove a lower bound of Ω((kn)^{3/4}).

Original language | English |
---|---|

Pages (from-to) | 395-402 |

Number of pages | 8 |

Journal | Lecture Notes in Computer Science |

Volume | 3383 |

Publication status | Published - 1 Dec 2004 |

Event | 12th International Symposium on Graph Drawing, GD 2004 - New York, United States of America Duration: 29 Sep 2004 → 2 Oct 2004 |

### Cite this

*Lecture Notes in Computer Science*,

*3383*, 395-402.