Information Technology Reference
In-Depth Information
at least one vertex. But
ξ
(
e
)
includes the same set of vertices of
V
inside it (and has the
same cost) as does
ξ
(
e
)
, although it has fewer faces, contradicting the choice for
e
=(
x
,
y
)
.
In case (a2) the edge
e
=(
x
,
z
)
is a non-tree edge since
T
contains no cycles. The inside
of
ξ
(
e
)
contains no more cost and one less face than
ξ
(
e
)
. If the cost inside
ξ
(
e
)
is greater
than the cost outside,
e
would have been chosen instead of
e
. On the other hand, if the
cost inside
ξ
(
e
)
is at most the cost outside, since the latter is equal to the cost outside
ξ
(
e
)
,
which is at most
c
(
V
)
/
3, the cost inside
ξ
(
e
)
is at most
c
(
V
)
/
3. However, this contradicts
the assumption that
μ
(
e
∗
)
>
2
c
(
V
)
/
3foralledges
e
∗
.
Consider the case (b) in which neither edge
(
x
,
z
)
nor
(
y
,
z
)
is in
T
.(SeeFig.
12.8
(c).)
The edges
(
x
,
z
)
and
(
y
,
z
)
each define a cycle contained within
ξ
(
e
)
. Without loss of gen-
erality assume that the cycle defined by
(
x
,
z
)
has more cost on the inside of
ξ
(
e
)
than does
the cycle defined by
(
y
,
z
)
. Because the cost of vertices on the inside of the original cycle is
more than 2
c
(
V
)
/
3,thecostinsideandon
ξ
((
x
,
z
))
is more than
c
(
V
)
/
3. Thus, the cost
outside
ξ
((
x
,
z
))
is less than or equal to 2
c
(
V
)
/
3. If the cost inside
ξ
((
x
,
z
))
is also less
than or equal to 2
c
(
V
)
/
3, we have a contradiction. If greater than 2
c
(
V
)
/
3,
ξ
((
x
,
z
))
is a
cycle with fewer faces for which
μ
((
x
,
z
))
>
2
c
(
V
)
/
3, another contradiction.
The following theorem uses Lemma
12.6.2
together with a spanning tree constructed
through a breadth-first traversal of a connected planar graph to show the existence of a small
separator that divides the vertices into approximately two equal cost parts.
THEOREM
12.6.2
Let
G
=(
V
,
E
)
be an
N
-vertex planar graph having non-negative vertex
costs summing to
c
(
V
)
.Then,
V
can be partitioned into three sets,
A
,
B
,and
C
,suchthatnoedge
joinsverticesin
A
w
ith those in
B
, neither
A
nor
B
has cost exceeding
2
c
(
V
)
/
3
,and
C
contains
no more than
4
√
N
vertices.
Proof
We assume that
G
is connected. If not, embed it in the plane and add edges as
appropriate to make it connected. Assume that it has been triangulated, that is, every face
except for the outermost is a triangle.
Pick any vertex (call it the root) and perform a breadth-first traversal of
G
. This traversal
defines a
BFS spanning tree
T
of
G
.Avertex
v
has level
d
in this tree if the length of the
path from the root to
v
has
d
edges. There are no vertices at level
q
where
q
is the level one
larger than that of all vertices. Let
R
d
be the vertices at level
d
and let
r
d
=
|
R
d
|
.
The reader is asked to show that there is some level
m
such that the cost of vertices
at levels below and above
m
each is at most
c
(
V
)
/
2.
(Se
e Problem
12.9
.) Let
l
and
h
,
h
, be levels closest to
m
that contain at most
√
N
vertices. That is,
r
l
≤
√
N
and
l
≤
m
≤
r
h
≤
√
N
. There are such levels because level 0 contains a single vertex and there are none
at level
q
.
The vertices in
G
are partitioned into the following five sets: a)
L
=
d<l
R
d
,b)
R
l
,
c)
M
=
l<d<h
R
d
,d)
R
h
,ande)
H
=
h<d
R
d
.Since
L
and
H
are subsets of the
sets of vertices with levels
le
ss than and more than
m
,
c
(
L
)
,
c
(
H
)
≤
c
(
V
)
/
2. Also, by
√
N
.If
R
l
=
R
h
=
R
m
(which implies that
M
is empty and
l
=
h
=
m
), let
A
=
L
,
B
=
H
,and
C
=
R
l
=
R
h
.Then,
C
is a separator of size at
construction,
r
l
,
r
h
≤
most
√
N
and the theorem holds. If
l
=
h
,then
h
−
l
−
1
≥
0. Since each of the
h
−
l
−
1
levels between
l
and
h
has at least
√
N
+
1 vertices, it follows that
h
√
N
−
l
−
1
≤
−
1
because these levels cannot have more than
N
1 vertices altogether.
Consider the subgraph of
G
consisting of the vertices in
M
and the edges between them.
Add a new vertex
v
0
to replace the vertices in
L
−
∪
R
l
and add an edge from
v
0
to each of
Search WWH ::
Custom Search