Information Technology Reference
In-Depth Information
3
Application: The Tangled-Thrackle Conjecture
Let
G
be tangled-thrackle with
n
vertices. By slightly modifying the edges (i.e., Jordan
arcs) near the points of tangencies, we obtain a simple topological graph
G
with the
same number of vertices and edges such that every pair of tangent edges in
G
become
disjoint in
G
and all other intersection points between edges remain the same. In order
to show that
O
(
n
), invoking Theorem 1, it suffices to prove the following.
Lemma 3.
Fo r every tangled-thrackle
G
,thesimple topological graph
G
does not con-
tainaset of 200 edges all disjointfromanother set of 200 edges.
|
E
(
G
)
|≤
Before proving the lemma, we briefly review the concept of Devenport-Schinzel se-
quences and arrangements of pseudo-segments.
A finite sequence
U
=(
u
1
,...,u
t
) of symbols over a finite alphabet is a
Davenport-
Schinzel sequence of order
s
if it satisfies the following two properties:
-
no two consecutive symbols in the sequence are equal to each other;
-
for any two distinct letters of the alphabet,
a
and
b
,thesequence does not contain
a (not necessarily consecutive) subsequence (
a,b,a,...,b,a
) consisting of
s
+2
symbols alternating between
a
and
b
.
The maximumlength of a Davenport-Schinzel sequence of order
s
over an alpha-
bet of size
n
is denoted
ʻ
s
(
n
). Sharp asymptotic bounds for
ʻ
s
(
n
) were obtained by
Nivasch [6] and Pettie [13]. However, to avoid the constants hidden in the big-Oh no-
tation, we use simpler explicit bounds. Specifically, we use the followingupper bound
for
ʻ
3
(
n
).
Theorem 7 (see Proposition 7.1.1 in [5]).
ʻ
3
(
n
)
<
2
n
ln
n
+3
n
.
of
m
Jordan arcs in the plane is called an
arrangementofpseudo-segment
if each pair of arcs intersects in at most one point (at an endpoint, a crossing,ora
point of tangency), and no three arcs have a common interior point. An arrangement
of pseudo-segments naturally defines a plane graph: The
vertices
of the arrangement
are the endpoints and the intersection points of the Jordan arcs, and the
edges
are the
portions of the Jordan arcs between consecutive vertices. The
faces
of the arrangement
are the connected components of the complement of the union of the Jordan arcs. The
vertices and edges are said to be
incidentto
a face if they are contained in the (topolog-
ical) closure of that face. The following theorem is a particular case of Theorem 5.3 of
[14].
Aset
L
Theorem 8 (see [14]).
Let
L
be an arrangementof
m
pseudo-segments and
F
be a
face of
L
.Then number of edges incidentto
F
is at most
ʻ
3
(2
m
)
.
Lemma 4.
Let
L
1
∪L
2
be an arrangementofpseudo-segments such thateveryarc in
L
1
is tangenttoall arcs in
L
2
; and
L
1
and
L
2
each formaconnected arrangement.
Then
L
1
or
L
2
contains at most 200 arcs.
Proof:
Suppose to the contrary, that both
L
1
and
L
2
contain at least 200 arcs. Without
loss of generality, we may assume
|L
1
|
=
|L
2
|
= 200. Since no arc in
L
1
crosses any
