Information Technology Reference
In-Depth Information
r
4
r
3
r
2
v
4
r
1
v
3
t
4
t
1
t
2
t
3
w
4
w
3
w
1
v
1
w
2
v
2
s
4
s
2
u
4
u
3
s
3
s
1
u
1
u
2
r
5
Fig. 7.
An example of how
γ
is chosen in the proof of Theorem 2 where
q
=5.Note
that forcing
r
5
(bottom left) below the
x
-axis causes the edge
{w
4
,r
5
}
to intersect
another edge.
[
ˁ
(
a
)
,ˁ
(
b
)] be the
x
-interval of edge
{
a, b
}
.Fortwoedges
{
a, b
}
and
{
c, d
}
in
H
where
a
,
b
,
c
,and
d
are distinct vertices in
R
,
ˁ
(
a, b
)
:otherwise,by
choosing
ʳ
appropriately we can cause the edges to intersect within their shared
x
-interval. This implies, for example, that the
x
-interval spanned by marked
vertices in one subtree does not intersect that of a different subtree.
For
H
1
,since
ˁ
(
s
1
,t
1
)
∩
ˁ
(
c, d
)=
∅
,
ˁ
(
t
1
)is
between ˁ
(
r
1
,s
1
)and
ˁ
(
u
1
,v
1
) (meaning either
ˁ
(
r
1
,s
1
)
<ˁ
(
t
1
)
<ˁ
(
u
1
,v
1
)or
ˁ
(
u
1
,v
1
)
<ˁ
(
t
1
)
<ˁ
(
r
1
,s
1
), where
A<B
if for all
a
∩
ˁ
(
u
1
,v
1
)=
∅
and
ˁ
(
t
1
,u
1
)
∩
ˁ
(
r
1
,s
1
)=
∅
B
,
a<b
).
By similar reasoning,
ˁ
(
w
1
) is between
ˁ
(
t
1
)and
ˁ
(
u
1
,v
1
) or between
ˁ
(
t
1
)and
ˁ
(
r
1
,s
1
). Let us assume, by renaming vertices if necessary, that
ˁ
(
w
1
) is between
ˁ
(
t
1
)and
ˁ
(
u
1
,v
1
). See Fig. 7.
The basic idea is to choose
ʳ
so that vertices in
R
are close to the
x
-axis
(with
ʳ
(
u
i
)
<ʳ
(
s
i
)
<
0=
ʳ
(
w
i
)
<ʳ
(
t
i
)
<ʳ
(
v
i
) for all
i
except when mentioned
otherwise) and so that unmarked vertices are forced to be above the
x
-axis.
We set
ʳ
(
u
1
) to be negative and
ʳ
(
v
1
) to be positive (so
w
1
lies in the triangle
t
1
u
1
v
1
). This, together with the fact that
r
2
is connected to
s
2
, forces the edge
from
w
1
to
r
2
to be upward and thus
r
2
to be above the
x
-axis.
Consider the order of
ˁ
(
s
2
),
ˁ
(
t
2
)and
ˁ
(
u
2
,v
2
). If
ˁ
(
s
2
) is between
ˁ
(
t
2
)and
ˁ
(
u
2
,v
2
), then setting
ʳ
so that the path
t
2
,u
2
,v
2
is above
s
2
(
ʳ
(
t
2
)
<ʳ
(
v
2
)
<
0
<ʳ
(
s
2
)
<ʳ
(
u
2
)) causes the path to intersect
{r
2
,s
2
}
.Notethat
ˁ
(
u
2
,v
2
)
cannot be between
ˁ
(
t
2
)and
ˁ
(
s
2
)since
ˁ
(
u
2
,v
2
)
∩ ˁ
(
s
2
,t
2
)=
∅
. Hence,
ˁ
(
t
2
)
is between
ˁ
(
s
2
)and
ˁ
(
u
2
,v
2
). Now let us consider the possible positions of
ˁ
(
w
2
). If
ˁ
(
s
2
) is between
ˁ
(
w
2
)and
ˁ
(
t
2
), then setting
ʳ
so that the path
u
2
,t
2
,w
2
is above
s
2
(
ʳ
(
w
2
)
<ʳ
(
u
2
)
<
0
<ʳ
(
s
2
)
<ʳ
(
t
2
)) causes the path to
intersect
∈
A
and
b
∈
{
r
2
,s
2
}
.Notethat
ˁ
(
u
2
,v
2
) cannot be between
ˁ
(
w
2
)and
ˁ
(
t
2
)since
ˁ
(
u
2
,v
2
)
. Hence,
ˁ
(
w
2
) is between
ˁ
(
s
2
)and
ˁ
(
t
2
) or between
ˁ
(
t
2
)and
ˁ
(
u
2
,v
2
). In the first case, we set
ʳ
(
s
2
)
<
0=
ʳ
(
w
2
)
<ʳ
(
t
2
)sothe
edge from
w
2
to
r
3
is forced upward to avoid intersecting path
r
2
,s
2
,t
2
.Inthe
second case, we set
ʳ
so that the path
t
2
,u
2
,v
2
is below
w
2
(
ʳ
(
u
2
)
<
0=
ʳ
(
w
2
)
<
ʳ
(
t
2
)
<ʳ
(
v
2
)) and the edge from
w
2
to
r
3
is forced upward. By repeating this
argument, we force all the unmarked vertices as well as
r
q
to be above the
x
-axis.
Since
r
q
is marked, we derive a contradiction by setting
ʳ
(
r
q
)
<
0.
∩
ˁ
(
t
2
,w
2
)=
∅
