Disjoint Edges in Topological Graphs and the Tangled-Thrackle Conjecture - Graph Drawing - page 284

The condition that no t edges are pairwise disjoint means that the intersection graph
of the edges (Jordan arcs) contains no anti-cliqueofsize t ,orequivalently the com-
plement of the intersection graph of the edges is K t -free. In this paper, we consider a
weaker condition that the complement of the intersection graph of the edges is K t,t -
free, where t is a constant. This means that graph G has no set of t edges that

are all disjoint from another set of t edges. Since no such graph G contains 2 t pairwise
disjoint edges, [10] implies

∈ N

O ( n log 8 t− 8 n ).Our main result improves this

| E ( G ) |≤

upper bound to O ( n ).

Theorem 1. Let t be a constant. The maximum number of edges inasimple

topological graphwith n vertices that does not contain t edges all disjointfromanother
set of t edges is O ( n ) .

∈ N

Application to thrackles. More than 50 years ago, Conway asked what is the maximum
number of edges in an n -vertex thrackle , that is, a simple topological graph G in which
every two edges intersect, either at a common endpoint or at a proper crossing [1].
He conjectured that every n -vertex thrackle has at most n edges. The first linear upper
bound was obtained by Lovász, Pach, and Szegedy [4], who showed that all such graphs
have at most 2 n edges. This upper bound was successively improved, and the current
record is

167

117 n< 1 . 43 n duetoFulek and Pach [2].
As an application of Theorem 1, we prove the tangled-thrackle conjecture recently
raised by Pach, Radoicic, and Tóth [9]. A drawing of a graph G is a tangled-thrackle
if it satisfies conditions (a)-(c) of topological graphs and every pair of edges have pre-
cisely one point in common: either a common endpoint, or a proper crossing, or a point
of tangency. Note that such a drawing is not a topological graph duetotangencies.
Pach, Radoicic, and Tóth [9] showed that every n -vertex tangled-thrackle has at most
O ( n log 12 n ) edges, and described a construction with at least

| E ( G ) |≤

7 n/ 6

edges. They con-
jectured that the upper bound can be improved to O ( n ). Here, we settle this conjecture
in the affirmative.

Theorem 2. Every tangled-thrackle on n vertices has O ( n ) edges.

2 Disjoint Edges in Topological Graphs

In this section, we prove Theorem 1. We start with reviewing afewgraph theoretic
results usedinourargument. The following is a classic result in extremal graph theory
duetoKovári, Sós, and Turán.

Theorem 3 (see [8]). Let G =( V,E ) be agraph that does not contain K t,t as a
subgraph.Then

2 − 1 /t , where c 1 is an absolute constant.

| E ( G ) |≤ c 1 | V ( G ) |

Two edges in a graph are called independent if they do not share an endpoint. We
define the odd-crossing number odd-cr( G ) of a graph G to be the minimumnumber of
unordered pairs of edges that are independent and cross an odd number of times over all