Logo

Login | Create Account

No-Three-in-Line-in-3D

Pór, Attila and Wood, David R. (2004) No-Three-in-Line-in-3D. [Conference Paper]

Full text not available from this repository.

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 \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
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:610
Deposited By:Selbach, Anna
Deposited On:23 Aug 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=395

Repository Staff Only: item control page

References

1. Michael A. Adena, Derek A. Holton, and Patrick A. Kelly. Some thoughts on the no-three-in-line problem. In Proc. 2nd Australian Conf. on Combinatorial Mathematics, vol. 403 of Lecture Notes in Math., pp. 6-17. Springer, 1974.

2. David Brent Anderson. Update on the no-three-in-line problem. J. Combin. Theory Ser. A, 27(3):365-366, 1979.

3. Roger C. Baker, Glyn Harman, and János Pintz. The difference between consecutive primes. II. Proc. London Math. Soc., 83(3):532-562, 2001.

4. Prosenjit Bose, Jurek Czyzowicz, Pat Morin, and David R. Wood. The maximum number of edges in a three-dimensional grid-drawing. J. Graph Algorithms Appl., 8(1):21-26, 2004.

5. Tiziana Calamoneri and Andrea Sterbini. 3D straight-line grid drawing of 4-colorable graphs. Inform. Process. Lett., 63(2):97-102, 1997.

6. Robert F. Cohen, Peter Eades, Tao Lin, and Frank Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1996.

7. D. Craggs and R. Hughes-Jones. On the no-three-in-line problem. J. Combinatorial Theory Ser. A, 20(3):363-364, 1976.

8. Emilio Di Giacomo. Drawing series-parallel graphs on restricted integer 3D grids. In Liotta [22], pp. 238-246.

9. Emilio di Giacomo and Henk Meijer. Track drawings of graphs with constant queue number. In Liotta [22], pp. 214-225.

10. Henry Ernest Dudeney. Amusements in Mathematics. Nelson, Edinburgh, 1917.

11. Vida Dujmovic, Pat Morin and David R. Wood. Layout of graphs with bounded tree-width. SIAM J. Comput., to appear.

12. Vida Dujmovic and David R. Wood. Three-dimensional grid drawings with subquadratic volume. In János Pach, ed., Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, pp. 55-66. Amer. Math. Soc., 2004.

13. Paul Erdös. A theorem of Sylvester and Schur. J. London Math. Soc., 9:282-288, 1934.

14. Paul Erdös. Appendix, in Klaus F. Roth, On a problem of Heilbronn. J. London Math. Soc., 26:198-204, 1951.

15. Stefan Felsner, Giuseppe Liotta, and Stephen Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl., 7(4):363-398, 2003.

16. Achim Flammenkamp. Progress in the no-three-in-line problem. II. J. Combin. Theory Ser. A, 81(1):108-113, 1998.

17. Richard K. Guy and Patrick A. Kelly. The no-three-in-line problem. Canad. Math. Bull., 11:527-531, 1968.

18. Richard R. Hall, Terence H. Jackson, Anthony Sudbery, and K. Wild. Some advances in the no-three-in-line problem. J. Combinatorial Theory Ser. A, 18:336-341, 1975.

19. Heiko Harborth, Philipp Oertel, and Thomas Prellberg. No-three-in-line for seventeen and nineteen. Discrete Math., 73(1-2):89-90, 1989.

20. Toru Hasunuma. Laying out iterated line digraphs using queues. In Liotta [22], pp. 202-213.

21. Torleiv Klove. On the no-three-in-line problem. III. J. Combin. Theory Ser. A, 26(1):82-83, 1979.

22. Giuseppe Liotta, ed., Proc. 11th International Symp. on Graph Drawing (GD'03), vol. 2912 of Lecture Notes in Comput. Sci. Springer, 2004.

23. János Pach, Torsten Thiele, and Géza Tóth. Three-dimensional grid drawings of graphs. In Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, eds., Advances in discrete and computational geometry, vol. 223 of Contemporary Mathematics, pp. 251-255. Amer. Math. Soc., 1999.

24. David R. Wood. Drawing a graph in a hybercube. Manuscript, 2004.

25. David R. Wood. Grid drawings of k-colourable graphs. Comput. Geom., to appear.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.