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
 
Search WWH ::




Custom Search