Information Technology Reference
In-Depth Information
c
3
n
log
8
t−
8
n
edges. By Lemma 2, there is a simple
topological graph
G
of maximumdegree at most
Δ
=
n
1
/
5
,
n
≤
By Theorem 5,
G
has
m
≤
n
+2
m/n
1
/
5
vertices, and
m
=
m
edges, such that the intersection graph of its edges is isomorphic
to that of
G
. Theorem 5 implies that
n
≤
n
+2
c
3
n
4
/
5
log
8
t−
8
n
.If
n
+2
m/n
1
/
5
≤
n
≥
n
0
for a sufficiently large constant
n
0
,then
n
≤
n
+2
c
3
n
4
/
5
log
8
t−
8
n
n
+
n
5
/
6
.
≤
(8)
Since
G
and
G
have the same number of edges, it is now enough to estimate
E
(
G
)
|
|
.
Note that
Δ
=
n
1
/
5
(
n
)
1
/
5
, and by Corollary 1, the bisection width of
G
is bounded
≤
by
1
4
t
1
4
t
1
4
t
.
b
(
G
)
c
5
(
n
)
1
−
c
5
(
n
+
n
5
/
6
)
1
−
2
c
5
n
1
−
≤
≤
≤
Partition the vertex set of
G
as
V
=
V
1
∪
1
V
|≤
2
V
|
for
i
=1
,
2,such that
G
has
b
(
G
) edges between
V
1
and
V
2
. Denote by
G
1
and
G
2
the
subgraphs induced by
V
1
and
V
2
, respectively. Put
n
1
=
V
2
with
3
|
V
i
≤
3
|
|
V
1
|
and
n
2
=
|
V
2
|
,where
n
1
+
n
2
=
n
≤
n
+
n
5
/
6
.
Note that both
G
1
and
G
2
are simple topological graphs that do not contain
t
edges
all disjoint from another set of
t
edges. By the induction hypothesis,
|
E
(
G
i
)
|≤
c
6
(
n
i
−
n
1
−
1
/
7
t
i
) for
i
=1
,
2. The total number of edges in
G
1
and
G
2
is
1
7
t
1
7
t
n
1
−
n
1
−
|
E
(
G
1
)
|
+
|
E
(
G
2
)
|≤
c
6
(
n
1
−
)+
c
6
(
n
2
−
)
1
2
1
7
t
1
7
t
c
6
(
n
1
−
+
n
1
−
≤
c
6
(
n
1
+
n
2
)
−
)
1
2
c
6
n
1
n
7
t
(
n
)
1
−
1
−
+
n
2
n
1
−
1
7
t
1
1
7
t
c
6
(
n
)
≤
−
1
3
7
t
n
1
−
1
−
+
2
3
1
−
1
7
t
1
1
7
t
c
6
(
n
+
n
5
/
6
)
≤
−
c
6
1
7
t
=
c
6
(
n
+
n
5
/
6
)
c
6
ʱn
1
−
−
7
t
)+
c
6
n
5
/
6
7
t
,
n
1
−
1
1)
n
1
−
1
≤
c
6
(
n
−
−
(
ʱ
−
where we write
ʱ
=(1
/
3)
1
−
1
/
7
t
+(2
/
3)
1
−
1
/
7
t
for short. Note that for every
t
,
we have
ʱ>
1.Taking into account the edges between
V
1
and
V
2
, the total number of
edges in
G
(and hence
G
)is
∈
N
E
(
G
)
+
b
(
G
)
|
|
=
|
E
(
G
1
)
|
+
|
E
(
G
2
)
|
7
t
)+
c
6
n
5
/
6
7
t
+2
c
5
n
1
−
1
1
1
4
t
n
1
−
1)
n
1
−
≤
c
6
(
n
−
−
(
ʱ
−
7
t
)+
c
6
n
5
/
6
+
n
1
−
7
t
1
1
4
t
1
n
1
−
1)
n
1
−
≤
c
6
(
n
−
−
(
ʱ
−
1
7
t
)
,
n
1
−
≤
c
6
(
n
−
(9)
where the last inequality holds for
n
n
0
if
n
0
is sufficiently large (independent of
c
6
). This completes the induction step, hence the proof of Theorem 6.
≥
