Thrackle

Last updated

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]

Contents

Linear thrackles

Four Reinhardt polygons. Their diameters (blue) form linear thrackles. Reinhardt 15-gons.svg
Four Reinhardt polygons. Their diameters (blue) form 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. If a vertex v is connected to three or more edges vw, vx, and vy, at least one of those edges (say vw) lies on a line that separates two other edges. Then, w must have degree one, because no line segment ending at w, other than vw, can touch both vx and vy. Removing w and 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. [2] Based on Erdős' proof, one can infer that every linear thrackle is a pseudoforest. Every cycle of odd length may be arranged to form a linear thrackle, but this is not possible for an even-length cycle, because if one edge of the cycle is chosen arbitrarily then the other cycle vertices must lie alternatingly on opposite sides of the line through this edge.

Micha Perles provided another simple proof that linear thrackles have at most 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 not, 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. [3]

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 points in the plane can have at most n diametral pairs, answering a question posed in 1934 by Heinz Hopf and Erika Pannwitz. [4] Andrew Vázsonyi conjectured bounds on the number of diameter pairs in higher dimensions, generalizing this problem. [2]

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. [5] This graph contains as a subgraph the thrackle of diameter pairs. [6]

The diameters of the Reinhardt polygons form linear thrackles. An enumeration of linear thrackles may be used to solve the biggest little polygon problem, of finding an n-gon with maximum area relative to its diameter. [7]

Thrackle conjecture

Unsolved problem in mathematics:

Can a thrackle have more edges than vertices?

(more unsolved problems in mathematics)
A thrackle embedding of a 6-cycle graph. 6-cycle thrackle.png
A thrackle embedding of a 6-cycle graph.

John H. Conway conjectured that, in any thrackle, the number of edges is at most equal to the number of vertices. Conway himself used the terminology paths and spots (for edges and vertices respectively), so Conway's thrackle conjecture was originally stated in the form every thrackle has at least as many spots as paths. Conway offered a $1000 prize for proving or disproving this conjecture, as part of a set of prize problems also including Conway's 99-graph problem, the minimum spacing of Danzer sets, and the winner of Sylver coinage after the move 16. [8]

Equivalently, the thrackle conjecture may be stated as every thrackle is a pseudoforest. More specifically, if the thrackle conjecture is true, the thrackles may be exactly characterized by a result of Woodall: they are the pseudoforests in which there is no cycle of length four and at most one odd cycle. [1] [9]

It has been proved that every cycle graph other than C4 has a thrackle embedding, which shows that the conjecture is sharp. That is, there are thrackles having the same number of spots as paths. At the other extreme, the worst-case scenario is that the number of spots is twice the number of paths; this is also attainable.

The thrackle conjecture is known to be true for thrackles drawn in such a way that every edge is an x-monotone curve, crossed at most once by every vertical line. [3]

Known bounds

Lovász, Pach & Szegedy (1997) proved that every bipartite thrackle is a planar graph, although not drawn in a planar way. [1] As a consequence, they show that every thrackleable graph with n vertices has at most 2n − 3 edges. Since then, this bound has been improved several times. First, it was improved to 3(n − 1)/2, [10] and another improvement led to a bound of roughly 1.428n. [11] Moreover, the method used to prove the latter result yields for any ε > 0 a finite algorithm that either improves the bound to (1 + ε)n or disproves the conjecture. The current record is due to Xu (2021), who proved a bound of 1.393n. [12]

If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex. [9] Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.

Related Research Articles

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Erdős–Faber–Lovász conjecture</span>

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

<span class="mw-page-title-main">Geometric graph theory</span> Subfield of graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs". Geometric graphs are also known as spatial networks.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Crossing number (graph theory)</span> Fewest edge crossings in drawing of a graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In the study of graph algorithms, an implicit graph representation is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

<span class="mw-page-title-main">Harborth's conjecture</span> On graph drawing with integer edge lengths

In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which every edge is a straight segment of integer length. This conjecture is named after Heiko Harborth, and would strengthen Fáry's theorem on the existence of straight-line drawings for every planar graph. For this reason, a drawing with integer edge lengths is also known as an integral Fáry embedding. Despite much subsequent research, Harborth's conjecture remains unsolved.

In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

References

  1. 1 2 3 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 .
  2. 1 2 Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly , 53 (5): 248–250, doi:10.2307/2305092, JSTOR   2305092 .
  3. 1 2 Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly , 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR   2812285, S2CID   17558559 .
  4. ↑ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
  5. ↑ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
  6. ↑ For the fact that the rotating caliper graph contains all diameter pairs, see Shamos, Michael (1978), Computational Geometry (PDF), Doctoral dissertation, Yale University. For the fact that the diameter pairs form a thrackle, see, e.g., Pach & Sterling (2011).
  7. ↑ Graham, R. L. (1975), "The largest small hexagon" (PDF), Journal of Combinatorial Theory , Series A, 18 (2): 165–170, doi: 10.1016/0097-3165(75)90004-7 .
  8. ↑ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
  9. 1 2 Woodall, D. R. (1969), "Thrackles and deadlock", in Welsh, D. J. A. (ed.), Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR   0277421 .
  10. ↑ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi: 10.1007/PL00009495 , MR   1739605 .
  11. ↑ Fulek, R.; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry, 44 (6–7): 345–355, arXiv: 1002.3904 , doi:10.1007/978-3-642-18469-7_21, MR   2785903 .
  12. ↑ Xu, Yian (15 January 2021). "A New Upper Bound for Conway's Thrackles". Applied Mathematics and Computation. 389: 125573. doi:10.1016/j.amc.2020.125573. S2CID   222111854.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.