Information Technology Reference
In-Depth Information
T
T
T
T
(a)
(b)
Figure 12.7
Crossings obtained by translating infinitesimally to the northeast
T
copies of (a)
one crossing and (b) the four possible connections between two wires.
THEOREM
12.6.1
Let
f
(
T
M
be the function computed by a VLSI chip that realizes the FSM
M
in
T
steps. The planar circuit size over a basis
Ω=
{
h
:
X
2
→
X
}
of any function
f
computed
by
M
in
T
steps satisfies the following inequalities:
C
p
,
Ω
0
(
f
)=
O
(
AT
2
)
C
p
,
Ω
0
(
f
)=
O
(
A
2
T
)
If
M
is multilective of order
μ
,then
C
p
,
Ω
(
f
)
is replaced by
C
(
μ
)
p
,
Ω
(
f
)
.
It is important to note that these relationships between planar circuit size and the mea-
sures
AT
2
and
A
2
T
hold for all functions computed by VLSI algorithms, both multi-output
functions and predicates.
In the next section we develop the planar separator theorem that is used in the next section
to derive lower bounds on the planar circuit size of important problems.
12.6.3 The Planar Separator Theorem
The
planar separator theorem
applies to graphs
G
=(
V
,
E
)
for which a non-negative cost
function
c
is defined on
V
.Thecostof
V
, denoted,
c
(
V
)
, is the sum of the costs of every
vertex in
V
. The theorem states that the vertices of every planar graph
G
on
N
vertices can be
partitioned into three sets,
A
,
B
,and
C
such that no edge connects a vertex in
A
with one in
B
, the cost of vertices i
n
A
,
c
(
A
)
,andthosein
B
,
c
(
B
)
,satisfy
c
(
A
)
,
c
(
B
)
≤
2
c
(
V
)
/
3and
C
contains at most 4
√
N
vertices.
The following lemma uses the concept of the
spanning tree
of a graph, a tree that contains
every vertex of a connected graph
G
. It shows the existence of a cycle that divides a planar graph
into an “inside” and an “outside” containing about the same number of vertices. The
radius
of a rooted spanning tree is the number of edges on the longest path from the root to a vertex.
(See Problem
12.8
for an illustration of the following lemma.)
Search WWH ::
Custom Search