Next: Problem 31: Trapping Light
Up: The Open Problems Project
Previous: Problem 29: Hamiltonian Tetrahedralizations
Problem 30: Thrackles
 Statement
 What is the maximum number of edges in a thrackle?
A thrackle is a planar drawing of a graph of n vertices
by edges
which are smooth curves between vertices,
with the condition
that each pair of edges intersect at exactly one point, and have distinct
tangents there.
Another phrasing is that nonincident edges cross exactly once,
and no incident edges share an interior point.
 Origin
 Conway, late 1960's.
 Status/Conjectures
 Open.
Conway's conjecture is that the number edges cannot exceed n.
 Partial and Related Results
 The upper bound was lowered from
O(n^{3/2}) to 2n  3 in [LPS95],
and further lowered to
(3/2)(n  1) in [CN00].
The conjecture has long been known to be true for straightline
thrackles.
The conjecture was extended in [CN00]
to the claim that a thrackle on n vertices embedded on a surface
of genus g has at most n + 2g edges.
See [BMP05, Sec. 9.5] for a recent discussion and further references.
 Reward
 Conway offers a reward of $1,000 for a resolution.
 Appearances
 [MO01,Weh]
 Categories
 graphs; combinatorial geometry; graph drawing; geometric graphs
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001; 13 Dec. 2001; 18 Feb. 2002 (thanks to David Eppstein).
E. Demaine, 28 May 2002 (thanks to Stephan Wehner); J. O'Rourke, 22 Sep. 2005.
 BMP05

Peter Brass, William Moser, and János Pach.
Research Problems in Discrete Geometry.
Springer, 2005.
 CN00

G. Cairns and Y. Nikolayevsky.
Bounds for generalized thrackles.
Discrete Comput. Geom., 23(2):191206, 2000.
 LPS95

László Lovász, János Pach, and Mario Szegedy.
On conway's thrackle conjecture.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 147151,
1995.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 Weh

Stephan Wehner.
On the thrackle problem.
http://www.thrackle.org/thrackle.html.
Next: Problem 31: Trapping Light
Up: The Open Problems Project
Previous: Problem 29: Hamiltonian Tetrahedralizations
The Open Problems Project  December 04, 2015