next up previous
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(n3/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 straight-line 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.

Bibliography

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):191-206, 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 147-151, 1995.

MO01
J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

Weh
Stephan Wehner.
On the thrackle problem.
http://www.thrackle.org/thrackle.html.


next up previous
Next: Problem 31: Trapping Light Up: The Open Problems Project Previous: Problem 29: Hamiltonian Tetrahedralizations
The Open Problems Project - December 04, 2015