Information Technology Reference
In-Depth Information
y
=1
=
⃒
y
=0
G
G
Fig. 1.
Redrawing procedure
≤
y
≤
2. The part of any edgelying in the horizontal strip 0
1 consists of vertical
segments.
Since a homeomorphism neither creates nor removes intersections between edges,
G
and
G
are isomorphic and their edges have the same intersection pattern.
Next we transform
G
into a topological graph
G
by the following operations. Re-
flect the part of
G
that lies above the
y
=1line aboutthe
y
-axis. Replace the vertical
segments in the horizontal strip 0
1 by straight line segments that reconnect the
corresponding pairs on the line
y
=0and
y
=1, and perturb the segments if necessary
to avoid triple intersections. Notice that if any two edges cross in
G
(and
G
), then they
must cross an even number of times in
G
. Indeed, suppose the edges
e
1
and
e
2
cross
in
G
.Since
G
is simple, they share exactly one point in common. Let
k
i
denote the
number of times edge
e
i
crosses the horizontal strip for
i
≤
y
≤
1
,
2, and note that
k
i
must
be odd since the graph is bipartite. These
k
1
+
k
2
segments within the strip pairwise
∈
cross in
G
, creating
k
1
+
k
2
crossings. Since edge
e
i
now crosses itself
k
2
times in
G
,thereare
k
1
+
k
2
2
k
1
2
k
2
2
=
k
1
k
2
−
−
(3)
crossings between edges
e
1
and
e
2
within the strip, which is odd when
k
1
and
k
2
are
odd. Since
e
1
and
e
2
had one point in common outside the strip in both
G
and
G
,then
e
1
and
e
2
cross each other an even number of times in
G
. (Note that one can easily
eliminate self-intersections by local modifications around these crossings.)
Hence, the number of pairs of edges that are independent and cross an odd number
of times in
G
is at most the number of disjoint pairs of edges in
G
, which is in turn at
most
c
1
|
2
−
1
/t
by Theorem 3. Combined with (2), we have
E
(
G
)
|
c
1
(
c
3
n
log
8
t−
8
n
)
2
−
1
t
odd-cr(
G
)
≤
1
t
log
16
t−
8
n,
cn
2
−
≤