NoThreeinLinein3DPór, Attila and Wood, David R. (2004) NoThreeinLinein3D. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 395402(Official URL: http://dx.doi.org/10.1007/9783540318439_40). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_40
AbstractThe 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 \Theta (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 \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 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 \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 kcolourable graph on n vertices has a 3D drawing with O (n\sqrt{k}) volume. For the kpartite Turán graph, we prove a lower bound of \Omega((kn)^3/4). Research supported by NSERC and COMBSTRU.
Actions (login required)
