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 Kn 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 Kn is θ(n 3/2). This compares favourably to θ(n3) when edges are not allowed to cross. Generalising the construction for Kn, 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 |
---|---|
Title of host publication | Graph Drawing |
Subtitle of host publication | 12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers |
Editors | János Pach |
Place of Publication | Berlin Germany |
Publisher | Springer |
Pages | 395-402 |
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 Sep 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) | 0302-9743 |
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 |
|