Information Technology Reference
In-Depth Information
Lemma 1 ([9]).
For every
0
3
, if a graph can be drawn as a topological
graph such that each of its edges is crossed at most k times, then in a drawing
with that property and the least number of crossings every pair of edges intersects
at most once.
≤
k
≤
Let
G
be a graph and let
D
be a drawing of
G
as a topological graph. Let
D
be a drawing of
G
as a topological graph with the least number of crossings such
that every pair of crossing edges in
D
are also crossing in
D
. The following is
implied by the proof of Theorem 3.2 in [15].
Lemma 2.
There is no pair of edges e and e
in D
such that there are two
crossing points between them that are consecutive along e.
Lemma 3.
If every edge in D (and hence in D
) is crossed by at most k edges,
then every edge in D
contains fewer than
2
k
crossing points with other edges.
3 Proof of Theorem 4
Recall that we wish to show that
e
k
(
n
)
≤
(
k
+3)(
n
−
2), for 0
≤
k
≤
3. That
is, for every 0
3, if a graph
G
with
n>
2 vertices can be drawn such that
each of its edges crosses at most
k
edges (possibly several times), then
G
has at
most (
k
+3)(
n
≤
k
≤
−
2) edges. Theorem 3 (due to Pach and Toth) yields this edge
bound for
k
3, but under the stronger assumption that each edge is crossed
at most
k
times. As we see in the next section, for
k
≤
2, the assumption is not
really stronger, so that we can use Theorem 3 for these cases (though for
k
=0
and
k
= 1 direct proofs are easier). For
k
=3weneedamoresophisticated
discharging argument, detailed in Section 3.2.
≤
3.1 The Local Pair-Crossing Number and Bounding
e
k
for
k ≤
2
The
local crossing number
,lcr(
G
), of a graph
G
is the smallest
k
so that
G
can
be drawn with at most
k
crossings per edge. The
local pair-crossing number
,
lpcr(
G
), is the smallest
k
so that
G
has a drawing in which each edge is crossed
by at most
k
other edges. By definition, lpcr(
G
)
lcr(
G
). Following the hints
in [14], it is possible to construct a graph
G
for which lpcr(
G
)=4andlcr(
G
)=5,
therefore, the two local crossing numbers differ. This is in marked contrast to the
pair crossing number, which we cannot at this point separate from the standard
crossing number.
≤
Theorem 5.
If
lpcr(
G
)
≤
2
,then
lpcr(
G
)=lcr(
G
)
.
This leaves open the question whether equality holds for lpcr(
G
)=3.We
believe a counterexample is possible, implying that we cannot take the easy
route via the local crossing number to establish the bound of
e
3
.
Proof.
The statement is immediate for lpcr(
G
) = 0 (by definition), and follows
from Lemma 2 for lpcr(
G
)
≤
1. Therefore, suppose that
G
is a graph with
