Information Technology Reference
In-Depth Information
lpcr(
G
) = 2. Fix a drawing
D
of
G
in which every edge crosses at most two
other edges and (under this condition) the least possible number of crossings.
It follows from Lemma 3 that every edge in
D
is crossed at most three times.
We claim that every edge in
D
is crossed at most twice. Suppose for the sake of
contradiction that there is an edge
e
that is crossed exactly three times. Orient
e
arbitrarily and let
x
1
,x
2
,x
3
be the crossing points on
e
, in the order they
appear on
e
according to its orientation. Denote by
e
1
,e
2
,e
3
the edges that
cross
e
at
x
1
,x
2
,x
3
, respectively. It follows from Lemma 2 that
e
1
=
e
3
and
e
1
=
e
2
. Moreover, by the same argument, the segment of
e
1
between
x
1
and
x
3
must contain a crossing point of
e
1
with an edge
e
. Note also that
e
crosses
e
1
once and
e
crosses
e
2
once, since
e
and
e
1
cross each other twice and there are at
most three crossing points on every edge. Denote by
D
the topological graph we
obtain by swapping the segments of
e
and
e
1
between
x
1
and
x
3
and redrawing
them at small neighborhoods of
x
1
and
x
3
such that these segments are disjoint
(see Fig. 1 for an illustration). Note that in
D
every edge still crosses at most
e
e
e
e
x
2
x
3
x
2
x
1
e
2
e
2
e
1
e
1
(a) before
(b) after
Fig. 1.
Decreasing the number of crossings in case of an edge that is crossed three
times
two other edges, however,
D
has fewer crossing points than
D
, contradicting
the minimality of
D
.
Thus, every edge in
D
is crossed at most twice, showing that lcr(
G
)
≤
2.
For
k ≤
2, we can now conclude that
e
k
(
n
)
≤
(
k
+3)(
n −
2) as follows: By
Theorem 5, if a graph
G
can be drawn so that each of its edges crosses at most
k
2 other edges, then
G
has a drawing in which each of its edges is crossed at
most
k
times; by Lemma 1, we can assume that
G
has such a drawing which is
simple. Now Theorem 4 yields the desired bound
e
k
(
n
)
≤
e
∗
(
n
)=(
k
+3)(
n
2).
The local pair-crossing number seems to be a useful tool for approaching
arguments about the pair-crossing number, so we would like to know more about
its properties. For example, one can ask whether lcr can be bounded in lpcr?
This is true, by Lemma 3, which yields the exponential bound lcr(
G
)
<
2
lpcr(
G
)
,
however, we think that much better bounds should be true, since we have much
more flexibility with the local pair-crossing number than with string graphs.
In particular, it would bear investigating whether the upper bounds achieved
by Toth and Matousek (bounding the crossing number in a function of the
pair-crossing number), aren't really arguments about the local version of these
crossing numbers.
≤
−
