Information Technology Reference
In-Depth Information
for
k
=3,namely,
e
3
(
n
)
≤
5
.
5
n
−
11. Ackerman [1] proved that
e
4
(
n
)
≤
6
n
−
12.
The last two bounds are tight up to an additive constant.
The bounds
e
k
(
n
) are used to get a weak lower bound on the crossing number
of the form cr(
G
)
≥
ʱ
|
E
(
G
)
|−
ʲ
|
V
(
G
)
|
. This linear bound is then used instead
of the trivial bound cr(
G
)
in the well-known probabilistic
proof of the Crossing Lemma. The same approach would work to get a better
lower bound for the pair-crossing number (and its variant pcr
+
), if one can show
that a sparse graph has an edge that crosses several other edges (each of them
possiblymanytimes).
Denote by
e
k
(
n
) 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).
2
Clearly,
e
k
(
n
)
≥|
E
(
G
)
|−
3
|
V
(
G
)
|
e
k
(
n
). For 0
≥
e
k
(
n
)
≥
≤
k
≤
3we
have the following upper bounds on
e
k
(
n
).
Theorem 4.
Let G be a graph with n
3
vertices that can be drawn as a
topological graph in which every edge crosses at most k other edges (each of
them possibly more than once). If
0
≥
≤
k
≤
3
,thenG has at most
(
k
+3)(
n
−
2)
edges.
2 it is known that there are infinitely many values
of
n
for which one can draw a (simple) topological graph with
n
vertices and
(
k
+3)(
n
Note that for 0
≤
k
≤
2) edges such that every edge is crossed at most
k
times. Therefore,
the bounds for 0
−
2 in Theorem 4 are tight. On the other hand, our upper
bound for
e
3
(
n
) is inferior to the known bound on
e
3
(
n
).
≤
k
≤
Organization.
In Section 2 we collect some useful facts towards proving The-
orem 4. A sketch of the proof of this theorem is then presented in Section 3.
In Section 4 we recall how such a result can be used to get a better bound for
the pair-crossing number when adjacent crossings are not allowed. Due to space
limitation, some of the proofs are omitted or only sketched. The missing details
can be found in the full version of the paper.
2 Preliminaries
In this section we collect some useful facts towards proving Theorem 4. Since
we will be interested in the number of crossing pairs and the number of edges
crossing a single edge, we may assume henceforth that the topological graphs
that we consider have no three edges crossing at a single point. Indeed, if more
than two edges cross at a point
p
, then we can redraw these edges in a small
neighborhood of
p
such that no three of them cross at a point without changing
the set of edges that each of these edges cross.
Recall that Pach et al. [9] proved that
e
k
(
n
)=
e
k
(
n
), for 0
≤
k
≤
3. This is
implied by the following lemma.
2
Think of the double prime symbol as a
pair
of prime symbols. Note that adjacent
crossings are allowed and counted although for improving the crossing lemma for
pcr
+
it would suce to consider drawings without adjacent crossings.
