Thrackle

A thrackle is an embedding of a graph in the plane in which each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, they must cross at their intersection point: the intersection must be transverse.[1]

A special case of thrackles, the linear thrackles, restrict the edges to be drawn as straight line segments. One method for constructing a linear thrackle with any given set of points as vertices is to form an edge between each farthest pair of points. For a linear thrackle, each connected component contains at most one cycle, from which it follows that the number of edges is at most equal to the number of vertices.

John H. Conway conjectured more generally that every thrackle has at most as many edges as vertices. It is known that the number of edges is at most a constant times the number of vertices.

  1. ^ Lovász, L.; Pach, J.; Szegedy, M. (1997), "On Conway's thrackle conjecture", Discrete and Computational Geometry, 18 (4): 369–376, doi:10.1007/PL00009322, MR 1476318. A preliminary version of these results was reviewed in O'Rourke, J. (1995), "Computational geometry column 26", ACM SIGACT News, 26 (2): 15–17, arXiv:cs/9908007, doi:10.1145/202840.202842.