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. 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(n1), 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:

9783319272603

Publisher:

Springer

Date Published:

20180121

Start Page: 
160

End Page:

166

Sponsor: 
R. Fulek—Gratefully acknowledges support from Austrian Science Fund (FWF): M2281N35. J. Pach—Supported by Swiss National Science Foundation Grants 200021165977 and 200020162884

URL: 

DOI: 
10.1007/9783319739151_14

Open access: 
yes (repository) 