Hardware Reference
In-Depth Information
˚
W
E
!
E
pair
(6.5)
For example, as shown in Fig.
6.4
a, when the operator ˚ is applied to E
.1;3/
,the
following mapping is obtained:
˚.E
.1;3/
/
Df
.E
.1;3/
;E
.1;2/
/; .E
.1;3/
;E
.2;3/
/; .E
.1;2/
;E
.2;3/
/
g
:
and ˚ defined above, for any electrode E
.i;j /
on the layout, a
graph G
.i;j /
can be constructed as follows. First, a droplet is placed virtually on the
electrode E
.i;j /
and the corresponding CEG (E
group
.i;j /
) is obtained. By applying
operator
Using operators
C
to each element of E
group
.i;j /
,wegettheCPG(P
group
.i;j /
) that corre-
sponds to this virtual droplet. Each pin in P
group
.i;j /
is mapped to a node in G
.i;j /
.
By applying operator ˚ on E
, the set of electrode pairs E
pair
.i;j /
can be derived.
For each electrode pair .E
x
;E
y
/ in E
pair
.i;j /
, we apply operator
C
to it and get
the corresponding pin pair .P
x
;P
y
/, and add an edge between the two nodes that
represent P
x
and P
y
in the graph. This edge is labeled as
Link
.E
x
;E
y
/
.As.E
x
;E
y
/
is an unordered pair, we consider the edges with labels
Link
.E
x
;E
y
/
and
Link
.E
y
;E
x
/
as the same edge, i.e., we do not distinguish between them.
In this way, a one-to-one mapping from the set E
pair
.i;j /
to the edges in G
.i;j /
is defined. Figures
6.4
c-f show graphs G
.1;2/
, G
.1;3/
, G
.2;3/
,andG
.3;3/
,which
correspond to electrodes E
.1;2/
, E
.1;3/
, E
.2;3/
,andE
.3;3/
in Fig.
6.4
a, respectively.
If two or more elements in the CEG of E
.i;j /
share the same control pin, as in the
case of electrode E
.2;3/
shown in Fig.
6.4
a, graph G
.i;j /
will contain cyclic edges,
and there will be multiple edges between certain pairs of distinct nodes. Figure
6.4
e
shows the graph G
.2;3/
corresponding to electrode E
.2;3/
, which is a multigraph.
Based on above examples, we conclude that G
.i;j /
is a complete graph if
Constraint
1
in Lemma
6.1
is satisfied (i.e., the elements in the CEG of E
.i;j /
are
assigned to different pins). Hence the number of edges in the graph G
.i;j /
can be
derived from the number of nodes in G
.i;j /
(i.e., the number of elements in the
corresponding CEG).
For a given pin-assignment configuration, let the set of electrodes be defined as
E
layout
. By virtually placing a droplet on electrode E
x
2
E
layout
, the graph G
E
x
for any electrode can be derived. The graph for the pin-assignment configuration,
which is written as G
layout
,isdefinedasthe
union
of all G
E
x
(E
x
2
E
layout
), i.e.,
G
layout
D
C
S
G
E
x
, where the set of nodes in G
layout
is obtained by applying
E
x
2
E
layout
the union operation to the set of graphs in G
E
x
;
8
E
x
2
E
layout
. In the union graph,
edges with the same label are considered as the same edge [
12
].
Next, we use two examples to illustrate the
union
of two graphs. Figure
6.5
a
shows the
union
of graphs G
.1;2/
and G
.1;3/
. Graphs G
.1;2/
and G
.1;3/
can be found
in Fig.
6.4
c and d, respectively. Note that the edge between nodes B and C in G
.1;2/
and the edge between nodes B and C in G
.1;3/
are both labeled as
Link
.E
.1;2/
;E
.1;3/
/
,
hence they are considered to be the same edge in the merged graph. In the merged
graph G
.1;2/
[
G
.1;3/
, there is only one edge
Link
.E
.1;2/
;E
.1;3/
/
between nodes B and C.
We find that the merged graph is a simple graph after checking the number of edges
between each pair of nodes.
