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. 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.
Linear thrackles
A linear thrackle is a thrackle drawn in such a way that its edges are straight line segments. As Paul Erdős observed, every linear thrackle has at most as many edges as vertices. Erdős's proof involves considering the special case of a linear thrackle that contains a vertex v {\displaystyle v} that forms the endpoint of three or more edges v w {\displaystyle vw} , v x {\displaystyle vx} , and v y {\displaystyle vy} . If two of these edges belonged to the same line, then no other edge could cross both, so at least one of these three edges (say v w {\displaystyle vw} ) must lie on a line that separates two other edges. Then, w {\displaystyle w} must have degree one, because no line segment ending at w {\displaystyle w} , other than v w {\displaystyle vw} , can touch both v x {\displaystyle vx} and v y {\displaystyle vy} . Removing w {\displaystyle w} and v w {\displaystyle vw} produces a smaller thrackle, without changing the difference between the numbers of edges and vertices. After removals like this lead to a thrackle in which every vertex has at most two neighbors, by the handshaking lemma the number of edges is at most the number of vertices. Based on Erdős' proof, one can infer that every linear thrackle is a pseudoforest, that is, a graph in which each connected component has at most one cycle. There exist linear thrackles in the form of cycles of each odd length. However, no linear thrackle can contain an even-length cycle. For, if one edge of a linear thrackle in the form of a cycle is chosen arbitrarily, then the other cycle vertices must lie alternatingly on opposite sides of the line through this edge. For an even cycle this alternation would cause the two edges adjacent to the chosen edge to be separated from each other by the line through the chosen edge. Micha Perles provided another simple proof that n {\displaystyle n} -vertex linear thrackles have at most n {\displaystyle n} edges, based on the fact that in a linear thrackle every edge has an endpoint at which the edges span an angle of at most 180°, and for which it is the most clockwise edge within this span. For, if an edge of a linear thrackle did not have this property, there would be two edges, incident to opposite endpoints of the edge and lying on opposite sides of the line through the edge, which could not cross each other. But each vertex can only have this property with respect to a single edge, so the number of edges is at most equal to the number of vertices. As Erdős also observed, the set of pairs of points realizing the diameter of a point set must form a linear thrackle: no two diameters can be disjoint from each other, because if they were then their four endpoints would have a pair at farther distance apart than the two disjoint edges. For this reason, every set of n {\displaystyle n} points in the plane can have at most n {\displaystyle n} diametral pairs, answering a question posed in 1934 by Heinz Hopf and Erika Pannwitz. Andrew Vázsonyi conjectured bounds on the number of diameter pairs in higher dimensions, generalizing this problem. In computational geometry, the method of rotating calipers can be used to form a linear thrackle from any set of points in convex position, by connecting pairs of points that support parallel lines tangent to the convex hull of the points. This graph contains as a subgraph the thrackle of diameter pairs. The diameters of the Reinhardt polygons form linear thrackles with equal numbers of edges and vertices. An enumeration of linear thrackles may be used to solve the biggest little polygon problem, of finding an n {\displaystyle n} -gon with maximum area relative to its diameter.
Thrackle conjecture
… excerpt ends here. Continue reading the full article.
