Thrackles: An Improved Upper Bound.Fulek, Radoslav and Pach, János (2017) Thrackles: An Improved Upper Bound. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 160168(Official URL: https://doi.org/10.1007/9783319739151_14). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_14
AbstractA thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasithrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasithrackle on n vertices is 3/2(n−1), and that this bound is best possible for infinitely many values of n.
Actions (login required)
