Saha, Indranil; Bhattacharya, Bhargab B.; Zhang, Sheng; Seth, Sharad C. Planar straight-line embedding of double-tree ccan architecture on a rectangular grid. (English) Zbl 1167.68414 Fundam. Inform. 89, No. 2-3, 331-344 (2008). 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 Keywords:DTS architecture; graph drawing; planar straight-line embedding PDFBibTeX XMLCite \textit{I. Saha} et al., Fundam. Inform. 89, No. 2--3, 331--344 (2008; Zbl 1167.68414)