Name
Title | ||
|---|---|---|
Planar Straight-Line Embedding of Double-Tree Scan Architecture on a Rectangular Grid |
Abstract | ||
|---|---|---|
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 &frac32;. 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. |
Year | Venue | Keywords |
|---|---|---|
2008 | Fundam. Inform. | partial dts,double-tree scan architecture,rectangular grid,nodes n,benchmark circuit,aspect ratio,grid point,planar straight-line embedding,full dts,double-tree graph,vlsi circuit,double-tree scan-paths,graph drawing |
Field | DocType | Volume |
Graph drawing,Discrete mathematics,Line (geometry),Combinatorics,Embedding,Binary tree,Planar,Very-large-scale integration,Mathematics,Grid,Whippletree | Journal | 89 |
Issue | ISSN | Citations |
2-3 | 0169-2968 | 2 |
PageRank | References | Authors |
0.37 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Indranil Saha | 1 | 296 | 18.27 |
| Bhargab B. Bhattacharya | 2 | 848 | 118.02 |
| Sheng Zhang | 3 | 2 | 0.37 |
| Sharad C. Seth | 4 | 671 | 93.61 |