Double-tree-scan (DTS) is a new scan-path architecture that is
deemed to be suitable for low-power testing of VLSI circuits. A full DTS
resembles two complete k-level (k > 0) binary trees whose leaf nodes are
merged pair-wise, and thus consists of exactly N
_{k}
= 3 × 2
^{k}
− 2
nodes. In this paper, the problem of planar straight-line embedding of a
"double-tree graph" on a rectangular grid is
investigated and an O(N
_{k}
) time algorithm for drawing it, is described. The
embedding requires at most 2N
_{k}
grid points, with an aspect ratio lying between
1 and �. Next, techniques of embedding a partial DTS is considered when the
number of nodes n ≠ 3 × 2
^{k}
− 2, for some k. Layouts of
double-tree scan-paths for some benchmark circuits are also presented to
demonstrate the results.
