Information Technology Reference
In-Depth Information
Rule +:
adjacent crossings are not allowed.
Rule -:
adjacent crossings are allowed but not counted.
Rule 0:
adjacent crossings are allowed and counted (this is the default rule).
Clearly, pcr
−
(
G
)
cr
+
(
G
)=cr(
G
) for every graph
G
. On the other hand, it is known [7] that cr(
G
)=
O
(pcr(
G
)
3
/
2
log
2
pcr(
G
)),
and it follows from the results in [13] that cr(
G
)
≤
pcr(
G
)
≤
pcr
+
(
G
)
≤
2
. Perhaps the
main related open problem is to determine whether there is a graph
G
for which
pcr(
G
)
<
cr(
G
).
The following lower bound on the crossing number was proved by Ajtai,
Chvatal, Newborn, Szemeredi [4] and, independently, by Leighton [6].
2
pcr
−
(
G
)
≤
Theorem 1 ([4,6]).
There is an absolute constant c>
0
such that for every
graph G with n vertices and m
c
m
3
n
2
.
This celebrated result is known as the
Crossing Lemma
and has numer-
ous applications in combinatorial and computational geometry, number theory,
and other fields of mathematics. The Crossing Lemma is tight, apart from the
multiplicative constant
c
. This constant was originally small, and later was
shown to be at least 1
/
64
≥
4
n edges we have cr
(
G
)
≥
0
.
0156, by a very elegant probabilistic argu-
ment due to Chazelle, Sharir, and Welzl [3]. Pach and Toth [10] proved that
0
.
0296
≈
7
.
5
n
). Their
lower bound was later improved by Pach, Radoicic, Tardos, and Toth [9] to
c
≈
1
/
33
.
75
≤
c
≤
0
.
09 (the lower bound applies for
m
≥
103
16
n
). Recently, Ackerman [1]
≥
1024
/
31827
≈
1
/
31
.
1
≈
0
.
0321 (when
m
≥
1
29
(when
m
further improved the lower bound to
c
6
.
95
n
).
Pach et al. [9] pointed out that the original proofs of the Crossing Lemma gen-
eralize to the pair-crossing number, yielding pcr(
G
)
≥
≥
3
64
|E
(
G
)
|
1
≥
2
when
|
E
(
G
)
|≥
|
V
(
G
)
|
4
. They also remarked that they were unable to extend their lower bound
on the crossing number to the pair-crossing number. Our main result is the
following.
|
V
(
G
)
|
Theorem 2.
For every graph G with n vertices and m
≥
6
.
75
n edges we have
2
6
3
7
m
3
m
3
1
34
.
2
pcr
+
(
G
)
n
2
.
All the above-mentioned improvements for the crossing number were obtained
using the same approach, namely, by showing that a sparse graph has an edge
that is involved in several crossings. Denote by
e
k
(
n
) the maximum number of
edges in a topological graph with
n>
2 vertices in which every edge is involved
in at most
k
crossings. Let
e
k
(
n
) denote the same quantity for
simple
topological
graphs. It follows from Euler's Polyhedral Formula that
e
0
(
n
)
≥
≥
n
2
≤
3
n
−
6. Pach and
4
.
108
√
kn
and also gave the following better bounds
Toth showed that
e
k
(
n
)
≤
for
k
≤
4.
Theorem 3 ([10]).
e
k
(
n
)
≤
(
k
+3)(
n
−
2)
for
0
≤
k
≤
4
. Moreover, these
bounds are tight when
0
≤
k
≤
2
for infinitely many values of n.
Pach et al. [9] observed that the upper bound in Theorem 3 applies also for
not necessarily simple topological graphs when
k
≤
3, and proved a better bound
