Title :
On wiring overlap layouts
Author_Institution :
Technol. Inst., Northwestern Univ., Evanston, IL, USA
Abstract :
A layout model called vertical-two-overlap is introduced. The following results are established for an arbitrary vertical-two-overlap layout W with area A. 1. A linear time algorithm for obtaining a two-layer wiring of W, if one exists, is devised. Also, by increasing the area to at most 2A a two-layer wirable layout is obtained. 2. To decide three-layer wirability of an arbitrary vertical-two-overlap layout is NP-complete. However, W can be converted into a three-layer wirable layout with area at most 3/2 A. 3. W is always four-layer wirable and a four-layer wiring thereof can be constructed in O(A) time
Keywords :
VLSI; circuit layout; computational complexity; network topology; trees (mathematics); NP-complete; edge disjoint trees; four-layer wiring; knock knee layout; layout model; linear time algorithm; three-layer wirability; two-layer wirable layout; vertical-two-overlap; wiring overlap layouts; Joining processes; Knee; Law; Legal factors; Tiles; Tree graphs; Wire; Wiring;
Conference_Titel :
VLSI, 1991. Proceedings., First Great Lakes Symposium on
Conference_Location :
Kalamazoo, MI
Print_ISBN :
0-8186-2170-2
DOI :
10.1109/GLSV.1991.143937
