Information Technology Reference
In-Depth Information
where
c
is an absolute constant. Together with Theorem 4, we have
cn
2
−
t
log
16
t−
8
n
+
n
1
d
i
b
(
G
)
≤
c
2
log
n
i
=1
n
c
2
√
cn
1
−
1
2
t
log
8
t−
3
n
+
c
2
log
n
d
i
≤
i
=1
n
1
2
t
log
8
t−
3
n
+
c
4
log
n
c
4
n
1
−
≤
d
i
,
i
=1
where
c
4
is an absolute constant, as required.
If the maximumdegree of
G
is relatively small, we obtain a sublinear bound on the
bisection width.
Corollary 1.
Let
G
=(
V,E
)
be simple topologicalbipartite graph on
n
vertices with
vertex degrees
d
1
,...,d
n
≤
n
1
/
5
such that
G
does not containaset of
t
edges all
disjointfromanother set of
t
edges. Then
1
4
t
,
c
5
n
1
−
b
(
G
)
≤
(4)
where
c
5
is an absolute constant.
n
1
/
5
into (1), we have
Proof:
Substituting
d
i
≤
2
t
log
8
t−
3
n
+
c
4
log
n
n
c
4
n
1
−
1
b
(
G
)
≤
·
n
2
/
5
1
2
t
log
8
t−
3
n
+
c
4
n
7
/
10
log
n
≤ c
4
n
1
−
1
4
t
,
c
5
n
1
−
≤
(5)
for a sufficiently large constant
c
5
.
Vertex splitting for topological graphs.
Given a simple topological graph with
n
ver-
tices, we reduce the maximumdegree below
n
1
/
5
by a standard vertex splitting opera-
tion. Importantly, this operation can be performed such that it preserves the intersection
pattern of the edges.
Lemma 2.
Let
G
be a simple topological graphwith
n
vertices and
m
edges; andlet
Δ
2
m/n
.Then there is a simple topological graph
G
withmaximum degree at most
Δ
, at most
n
+2
m/Δ
vertices, and precisely
m
edges such thattheintersectiongraph
of its edges is isomorphic to thatof
G
.
≥
Proof:
We successively split every vertex in
G
whose degree exceeds
Δ
as follows.
Refer to Fig.2.Let
v
be a vertex of degree
d
(
v
)=
d>Δ
,andlet
vu
1
,vu
2
,...,vu
d
be the edges incident to
v
in counterclockwise order. In a small neighborhood around
v
,
replace
v
by
d/Δ
new vertices,
v
1
,...,v
d/ʔ
placed in counterclockwise order on a
