No-three-in-line-in-3D

Attila Pór; David R. Wood

doi:10.1007/978-3-540-31843-9_40

No-three-in-line-in-3D

Attila Pór, David R. Wood

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

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 ²). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint in ℤ³, 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³) when edges are not allowed to cross. Generalising the construction for Kⁿ, 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	https://doi.org/10.1007/978-3-540-31843-9_40
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	United States of America
City	New York
Period	29/09/04 → 2/10/04
Internet address	https://link.springer.com/book/10.1007/b105810 (Proceedings)

Access to Document

10.1007/978-3-540-31843-9_40

Link to publication in Scopus

Cite this

@inproceedings{843a4bdf23304fb88bd8c4377f26f7aa,

title = "No-three-in-line-in-3D",

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{\"o}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{\'a}n graph, we prove a lower bound of Ω((kn)3/4).",

author = "Attila P{\'o}r and Wood, {David R.}",

year = "2004",

month = dec,

day = "1",

doi = "10.1007/978-3-540-31843-9_40",

language = "English",

isbn = "3540245286",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "395--402",

editor = "J{\'a}nos Pach",

booktitle = "Graph Drawing",

note = "Graph Drawing 2004, GD 2004 ; Conference date: 29-09-2004 Through 02-10-2004",

url = "https://link.springer.com/book/10.1007/b105810",

}

Pór, A & Wood, DR 2004, No-three-in-line-in-3D. in J Pach (ed.), Graph Drawing: 12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers. Lecture Notes in Computer Science, vol. 3383, Springer, Berlin Germany, pp. 395-402, Graph Drawing 2004, New York, United States of America, 29/09/04. https://doi.org/10.1007/978-3-540-31843-9_40

No-three-in-line-in-3D. / Pór, Attila; Wood, David R.

Graph Drawing: 12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers. ed. / János Pach. Berlin Germany : Springer, 2004. p. 395-402 (Lecture Notes in Computer Science; Vol. 3383).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - No-three-in-line-in-3D

AU - Pór, Attila

AU - Wood, David R.

N1 - Conference code: 12th

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=24144502886&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-31843-9_40

DO - 10.1007/978-3-540-31843-9_40

M3 - Conference Paper

AN - SCOPUS:24144502886

SN - 3540245286

T3 - Lecture Notes in Computer Science

SP - 395

EP - 402

BT - Graph Drawing

A2 - Pach, János

PB - Springer

CY - Berlin Germany

T2 - Graph Drawing 2004

Y2 - 29 September 2004 through 2 October 2004

ER -