**Next:** Problem 31: Trapping Light Rays with Segment Mirrors

**Previous:** Problem 29: Hamiltonian Tetrahedralizations

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