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 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

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.