Information Technology Reference
In-Depth Information
A
2
A
2
B
0
B
0
B
4
w
1
B
4
w
1
P
w
0
w
0
v
1
v
1
v
2
v
3
v
2
v
3
A
1
A
3
=
B
1
A
1
A
3
=
B
1
f
f
v
0
v
0
P
Y
v
4
v
4
y
4
t
4
x
4
t
4
X
A
4
=
B
2
A
4
=
B
2
A
0
=
B
3
A
0
=
B
3
(a) If [
v
4
v
0
] is not an edge of
t
4
,
then there are four
D
-edges that cross
(
A
0
,B
0
).
(b) If [
v
4
v
0
]isanedgeof
t
4
, then there
are four
D
-edges that cross (
A
4
,B
4
).
Fig. 5.
The 0-pentagon
f
contributes charge through [
v
0
v
1
]and[
v
1
v
2
]inStep2and
through [
v
2
v
3
], [
v
3
v
4
]and[
v
4
v
0
] in Step 3(b)
1
/
6 units of charge through each of its other three edges in Step 3(b). A simple
case-analysis shows that this scenario is impossible, as it implies that there is an
edge of
D
that crosses four other edges (see Fig. 5 for illustrations).
It follows from Lemma 4 that the final charge of every face in
M
(
D
) is nonneg-
ative and that the charge of every vertex of
D
equals to one third of its degree.
Recall that the total charge is 4
n
=
A∈V
(
D
) 3
deg(
A
)
8. Therefore,
3
|
≤
4
n −
8 and thus
|E
(
G
)
|
=
|E
(
D
)
|≤
6
n −
12. This concludes the proof of Theo-
rem 4.
−
E
(
D
)
|
4 A Better Lower Bound on pcr
+
Recall that
e
k
(
n
) is the maximum number of edges in a topological graph with
n>
2 vertices in which every edge crosses at most
k
other edges (each of them
possibly more than once). Using the bounds on
e
k
(
n
) from Theorem 4, one can
prove:
Theorem 6.
For every graph G with n>
2
vertices and m edges we have:
pcr
(
G
)
≥
m
−
3(
n
−
2)
;pcr
(
G
)
≥
2
m
−
7(
n
−
2)
;pcr
(
G
)
≥
3
m
−
12(
n
−
2)
;and
pcr
(
G
)
≥
4
m
−
18(
n
−
2)
.
Using the new linear bounds it is now possible to obtain a better lower bound
for pcr
+
, following the probabilistic proof of the Crossing Lemma, as in [8,9,10].
Proof of Theorem 2:
Let
G
be a graph with
n
vertices and
m
6
.
75
n
edges and
consider a drawing of
G
as a topological graph with pcr
+
(
G
) pairs of crossings
edges and without adjacent crossings. Construct a random subgraph of
G
by
selecting every vertex independently with probability
p
=6
.
75
n/m
≥
1. Let
G
be the subgraph of
G
that is induced by the selected vertices. Denote by
n
and
m
the number of vertices and edges in
G
, respectively. Clearly,
≤
[
n
]=
pn
E
[
m
]=
p
2
m
.Denoteby
x
the number of pairs of crossing edges in the
and
E
