Information Technology Reference
In-Depth Information
circle of small radius centered at
v
. Withoutintroducing any new crossings, connect
u
j
to
v
i
if and only if
Δ
(
i
−
1)
<j
≤
Δi
for
j
∈{
1
,...,d
}
and
i
∈{
1
,...,Δ
}
. Finally,
we do a local change within the small circle by moving each vertex
v
i
across the circle,
so that every edgeincidentto
v
i
crosses all edges incident to
v
i
,forall
i
=
i
.Asa
result, any two edges incident to some vertex
intersect precisely once:
either at a common endpoint or at a crossing within the small circle centered at
v
.
{
v
1
,...,v
d/ʔ
}
v
1
v
2
v
3
v
3
v
v
1
v
2
Fig. 2.
Splitting avertex
v
into new vertices
v
1
,v
2
,v
3
,such that each
v
i
has degree at most
ʔ
.
Moreover, we do not introduce any disjoint pairs of edges and ournewgraph remains simple.
After applying this procedure to all vertices
G
, we obtain a simple topological graph
G
of maximumdegree at most
Δ
. By construction,
G
has
m
edges, and the intersection
pattern of the edges is the same as in
G
.Thenumber of vertices in
G
is
d
(
v
)
Δ
n
+
v
d
(
v
)
Δ
≤
n
+
2
m
V
(
G
)
|
|≤
≤
Δ
,
v
∈
V
∈
V
as claimed.
Putting thingstogether.
Since all graphs have a bipartite subgraph with at least half of
its edges, Theorem 1 immediately follows from the following.
Theorem 6.
Let
G
be an
n
-vertex simple topologicalbipartite graph such that
G
does
not contain
t
edges all disjointfromanother set of
t
edges. Then
1
7
t
)
,
n
1
−
|
E
(
G
)
|≤
c
6
(
n
−
(6)
where
c
6
=
c
6
(
t
)
depends only on
t
.
Proof:
Let
t
be a constant. We proceed by induction on
n
.Let
n
0
=
n
0
(
t
) be a
sufficiently large constant (specified in (8) and (9) below) that depends only on
t
,and
on the constants
c
3
and
c
5
defined in Theorem 5 and Corollary 1, respectively. Let
c
6
be
asufficiently large constant such that
c
6
≥
∈
N
2
c
5
and for every positive integer
n
≤
n
0
,
we have
1
7
t
)
,
(7)
The choice of
n
0
and
c
6
ensures that (6) holds for all graphs with at most
n
0
vertices.
Now consider an integer
n>n
0
,andassume that (6) holds for all graphs with fewer
than
n
vertices. Let
G
be a simple topological bipartite graph with
n
vertices such that
G
does not contain
t
edges all disjoint from another set of
t
edges.
c
3
n
log
8
t−
8
n
n
1
−
≤
c
6
(
n
−
