Information Technology Reference
In-Depth Information
the vertices at level
l
+
1. This operation retains planarity and the resulting graph remains
triangulated because adjacent vertices on
R
l
+
1
have an edge between them. Also, it defines a
spanning tree
T
∗
consisting of
v
0
, the new edges, a
nd
the projection of the original spanning
tree to the vertices in
M
.
T
∗
has radius at most
√
N
.
Apply Lemma
12.6.2
to
T
∗
giving
v
0
zero cost. This lemma identifies three sets of
vertices,
A
0
,
B
0
and
C
0
, from which we delete
v
0
and adjacent edges. Since
c
(
M
)
≤
c
(
V
)
,
it follows that t
her
e are no edges between vertices in
A
0
and
B
0
,
c
(
A
0
)
,
c
(
B
0
)
≤
2
c
(
V
)
/
3,
4
√
N
.
Each of the four sets
A
0
,
B
0
,
L
,and
H
hascostatmost2
c
(
V
)
/
3. If any one of them
has cost more than
c
(
V
)
/
3, let it be
A
and let
B
be the union of the remaining sets. If none
of them has cost more than
c
(
V
)
/
3 vertices, order the sets by size and let
A
be the union of
the fewest of these sets whose cost is at least
c
(
V
)
/
3 vertices. This procedure insures that
A
has cost between
c
(
V
)
/
3and2
c
(
V
)
/
3 which implies that
B
satisfies the same condition as
A
and the theorem is established.
2
√
N
.Let
C
=
C
0
∪
|
C
0
|≤
R
l
∪
R
h
. It follows that
|
C
|≤
and
The preceding version of the planar separator theorem only guarantees that the vertices of a
planar graph are divided into two sets whose costs are nearly balanced and a small separator. It
does not insure that the number of vertices in the two sets are balanced. The following lemma
remedies this situation. We leave its proof to the reader. (See Problem
12.10
.)
LEMMA
12.6.3
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
,suchthatnoedgejoins
vertices in
A
with those in
B
, neit
her
A
nor
B
has cost exceedin
g
7
c
(
V
)
/
9
,
|
A
|
|
B
|≤
5
N/
6
,
,
and
C
contains no more than
K
1
√
N
vertices, where
K
1
=
4
(
2
/
3
+
1
)
.
This new result can be applied to show that the vertices of a planar graph can be partitioned
into many sets each having about the same cost and such that a small set of vertices can be
removed to separate each set from all other sets. This result is also left to the reader. (See
Problem
12.11
.)
LEMMA
12.6.4
Let
G
=(
V
,
E
)
be an
N
-vertex planar graph and let
c
be a non-negative cost
function on
V
w
ith total cost of
c
(
V
)
.Let
P
≥
2
. There are constants
2
P/
3
≤
q
≤
3
P
and
K
2
=
4
(
2
/
3
+
1
)
/
(
1
−
5
/
6
)
such that
V
can be partitioned into
q
sets,
A
1
,
A
2
,
...
,
A
q
≤
i
≤
q
such that for
1
c
(
V
)
/
(
3
P
)
≤
c
(
A
i
)
≤
3
c
(
V
)
/
(
2
P
)
K
2
√
N
,and
B
i
=
V
and there are sets
C
i
,
|
C
i
|≤
−
A
i
−
C
i
such that no edges join vertices in
A
i
with vertices in
B
i
.
12.7
The Performance of VLSI Algorithms
Using Theorem
12.6.1
and Lemma
12.6.4
,wenowderivelowerboundson
AT
2
and
A
2
T
for individual functions by deriving lower bounds on their planar circuit size. In the following
section we derive lower bounds to the planar circuit size for multi-output functions using the
w
(
u
,
v
)
-flow property of these functions. In Section
12.7.2
we set the stage for deriving lower
bounds on the planar circuit size of predicates.
Search WWH ::
Custom Search