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 25-27 , pp. 160-168(Official URL: https://doi.org/10.1007/978-3-319-73915-1_14).

Full text not available from this repository.

Abstract

A 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. Quasi-thrackles 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 quasi-thrackle on n vertices is 3/2(n−1), and that this bound is best possible for infinitely many values of n.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1601

Actions (login required)

View Item View Item