Pór, Attila and Wood, David R. (2004) No-Three-in-Line-in-3D. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 395-402(Official URL:

Full text not available from this repository.


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 \Theta (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 \Theta(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 \mathbb{Z}^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 \Theta(n^3/2). This compares favourably to \Theta (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\sqrt{k}) volume. For the k-partite Turán graph, we prove a lower bound of \Omega((kn)^3/4). Research supported by NSERC and COMBSTRU.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_40
Classifications: A General Literature > A.001 Introductory and Survey

Actions (login required)

View Item View Item