Thrackles: An Improved Upper Bound Conference Paper


Author(s): Fulek, Radoslav; Pach, János
Title: Thrackles: An Improved Upper Bound
Title Series: LNCS
Affiliation IST Austria
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.
Conference Title: GD: Graph Drawing and Network Visualization
Volume: 10692
Conference Dates: September 25 - 27, 2017
Conference Location: Boston, MA, USA
ISBN: 978-331927260-3
Publisher: Springer  
Date Published: 2018-01-21
Start Page: 160
End Page: 166
Sponsor: R. Fulek—Gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35. J. Pach—Supported by Swiss National Science Foundation Grants 200021-165977 and 200020-162884
URL:
DOI: 10.1007/978-3-319-73915-1_14
Open access: yes (repository)
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work