Information Technology Reference
In-Depth Information
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