Biomedical Engineering Reference
In-Depth Information
Figure 3.6
Mapping of an array to an undirected graph.
Our goal is to ensure that any five adjacent unit cells (i.e., a central cell
and its four neighbors) that form a “cross” are assigned distinct pins. We
refer to the preceding constraint as the “cross constraint.” The pin assign-
ment problem under cross constraints can be mapped to the well-known
vertex-coloring problem in graph theory [56]. The problem here is to obtain
a 5-coloring of the graph derived from a partition, as shown in Figure 3.6.
The unit cells in the partition are mapped to vertices, and any two cells that
belong to a cross are connected by an edge. The graph corresponding to a
partition is referred to as the
partition graph
.
The graph-coloring problem, which involves the determination of the chro-
matic number χ(
G
)
for a graph
G
, is known to be NP-complete [57]. However, if
χ(
G
) or the number of colors to be used is known, as is the case here, there exists
an efficient algorithm for graph coloring. Moreover, the regular structure of the
partitions can be used to solve the problem more efficiently using tiling.
This approach allows us to use a regular distribution of pins, a layout fea-
ture that is not directly obtained from graph coloring. The tile (or template)
used here is referred to as “Bagua,” a Chinese game strategy for the Connect-5
board game [61]. A Bagua is a tilted square, as shown in Figure 3.7. By repeat-
edly placing Bagua structures next to each other until the partition bound-
aries are reached, a Bagua repetition is derived, as shown in Figure 3.7. The
tiling using Bagua repetitions forms the basis for the Connect-5 algorithm.
1
1
1
1
1
1
1
Figure 3.7
A single Bagua structure (the tilted square) and its repetition in a square partition.
