×

Planar straight-line embedding of double-tree ccan architecture on a rectangular grid. (English) Zbl 1167.68414

Summary: 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\times 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 \(\frac32\). Next, techniques of embedding a partial DTS is considered when the number of nodes \(n\neq 3\times 2^k-2\), for some \(k\). Layouts of double-tree scan-paths for some benchmark circuits are also presented to demonstrate the results.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M07 Mathematical problems of computer architecture
PDFBibTeX XMLCite