Hardware Reference
In-Depth Information
Fig. 6.6 ( a ) Three categories of electrodes and the graphs correspond to electrodes of (b) the first
category ( c ) the second category ( c ) the third category
nodes and the number of edges is 2 =10. Since the number of such electrodes is
.m 2/ .n 2/, we will get .m 2/ .n 2/ complete graphs with 10 edges.
On the other hand, the number of edges that are contained in two graphs is .m
1/ n C .n 1/ m+2 .m 1/ .n 1/. Using the principle of inclusion/exclusion,
we set the total number of edge in the graph G layout to be:
N edge D 4 3 C 12.m C n 4/ C 10.mn 2m 2n C 4/
Œ.m 1/n C .n 1/m 2 .m 1/ .n 1/
D 6mn 5m 5n C 2
According to Lemma 6.2 , if the pin-assignment configuration satisfies both
Constraint 1 and Constraint 2 , then graph G layout is a simple graph. Assume that
there are M control pins in the pin-assignment configuration. The number of nodes
in graph G layout is equal to M . The maximum number of edges in the simple graph
G layout that has M nodes is given by:
N edge _max D M
2
! D
M .M 1/
2
Finally, we derive the desired lower bound in the number of control pins. Since
N edge _max is an upper limit on the number of edges in a graph, we have the inequality
N edge _max N edge .
Search WWH ::




Custom Search