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

Disjoint Edges in Topological Graphs
and the Tangled-Thrackle Conjecture

Andres J. Ruiz-Vargas 1 , Andrew Suk 2 , and Csaba D. Tóth 3

1

École polytechnique fédérale de Lausanne, Lausanne, Switzerland
[e-mail]

2

University of Illinois at Chicago, Chicago, IL, USA
[e-mail]

3

California State University Northridge, Los Angeles, CA, USA
[e-mail]

Abstract. It is shown that for a constant t ∈ N , every simple topological graph
on n vertices has O ( n ) edges if the graph has no two sets of t edges such that ev-
ery edge in one set is disjoint from all edges of the other set (i.e., the complement
of the intersection graph of the edges is K t,t -free). As an application, we settle
the tangled-thrackle conjecture formulated by Pach, Radoicic, and Tóth: Every
n -vertex graph drawn in the plane such that every pair of edges have precisely
one point in common, where this point is either a common endpoint, a crossing,
or a point of tangency, has at most O ( n ) edges.

1 Introduction

A topological graph is a graph drawn in the plane such that its vertices are represented
by distinct points and its edges are represented by Jordan arcs between the correspond-
ing points satisfying the following (nondegeneracy) conditions: (a) no edge intersects
any vertex other than its endpoints, (b) any two edges have only a finite number of inte-
rior points in common, (c) no three edges have a common interior point, and (d) if two
edges share an interior point, then they properly cross at that point [7]. A topological
graph is simple if every pair of edges intersect in at most one point. Two edges of a
topological graph cross if their interiors share a point, and are disjoint if they neither
share a common vertex nor cross.
In 2005, Pach and Tóth [10] conjectured that for every constant t

3,an n -vertex
simple topological graph has O ( n ) edges if no t edges are pairwise disjoint. They gave
an upper bound of

≥

O ( n log 4 t− 8 n ) for all such graphs. Despite much atten-
tion over the last 10 years (see related results in [3,11,15,16]), the conjecture is still
open.

| E ( G ) |≤

Work on this paper began at the AIM workshop Exact Crossing Numbers (Palo Alto, CA,
2014) . Research by Ruiz-Vargas was supported by the Swiss National Science Foundation
grants 200021-125287/1 and 200021-137574. Research by Sukwassupported by an NSF Post-
doctoral Fellowship and by the Swiss National Science Foundation grant 200021-125287/1.
Research by Tóth was supported in part by the NSF award CCF 1423615.