Information Technology Reference
In-Depth Information
topological drawingsof
G
.The
bisectionwidth
of a graph
G
, denoted by
b
(
G
),isthe
smallest nonnegative integer such that there is a partition of the vertex set
V
=
V
1
∪
V
2
1
2
=
b
(
G
). The following result,
duetoPach and Tóth, relates the odd-crossing number of a graph to its bisection width.
1
3
|
V
|≤
V
i
≤
3
|
V
|
for
i
=1
,
2,and
|
E
(
V
1
,V
2
)
|
with
Theorem 4 ([10]).
There is an absolute constant
c
2
such thatif
G
is agraphwith
n
vertices of vertex degrees
d
1
,...,d
n
,then
odd-cr(
G
)+
n
b
(
G
)
≤
c
2
log
n
d
i
.
i
=1
We also rely on the result duetoPach and Tóth [10] stated in the introduction.
Theorem 5 ([10]).
Let
G
=(
V,E
)
be an
n
-vertex simple topological graph,such that
G
does not contain
t
pairwise disjointedges. Then
c
3
n
log
4
t−
8
n
, where
c
3
|
E
(
G
)
|≤
is an absolute constant.
From disjointedges to odd crossings.
Using a combination of Theorems 3-5, we es-
tablish the following lemma.
Lemma 1.
Let
G
=(
V,E
)
be simple topologicalbipartite graph on
n
vertices with
vertex degrees
d
1
,...,d
n
,such that
G
does not containaset of
t
edges all disjointfrom
another set of
t
edges. Then
n
1
2
t
log
8
t−
3
n
+
c
4
log
n
c
4
n
1
−
d
i
,
b
(
G
)
≤
(1)
i
=1
where
c
4
is an absolute constant.
Proof:
Since
G
does not contain 2
t
pairwise disjoint edges, Theorem 5 yields
c
3
n
log
8
t−
8
n.
|
E
(
G
)
|≤
(2)
Let
V
a
and
V
b
be the vertex classes of the bipartite graph
G
. Consider a simple
curve
ʳ
that decomposes the plane into two parts, containing all points in
V
a
and
V
b
,
respectively. By applying asuitable homeomorphism to the plane that maps
ʳ
to a
horizontal line,
G
is deformed into a topological graph
G
such that (refer to Fig.1)
1. The vertices in
V
a
are above the line
y
=1, the vertices in
V
b
are below the line
y
=0,
1
Pach and Tóth [10] defined the odd-crossing number of a graph
G
to be the minimumnumber
of pairs of edges that cross an odd number of times (over all drawingsof
G
), including pairs of
edges with a common endpoint. However, since the number of pairs of edges with a common
endpoint is at most
i
=1
d
i
, this effects Theorem 4 only by a constant factor.
