Next: Problem 31: Trapping Light Rays with Segment Mirrors
Previous: Problem 29: Hamiltonian Tetrahedralizations
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.
Conway, late 1960’s.
Open. Conway’s conjecture is that the number edges cannot exceed n.
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.
Conway offers a reward of $1,000 for a resolution.
graphs; combinatorial geometry; graph drawing; geometric graphs
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.
Peter Brass, William Moser, and János Pach. Research Problems in Discrete Geometry. Springer, 2005.
G. Cairns and Y. Nikolayevsky. Bounds for generalized thrackles. Discrete Comput. Geom., 23(2):191–206, 2000.
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.
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.
Stephan Wehner. On the thrackle problem. http://www.thrackle.org/thrackle.html.