DocumentCode
3333737
Title
On wiring overlap layouts
Author
Chiang, Charles
Author_Institution
Technol. Inst., Northwestern Univ., Evanston, IL, USA
fYear
1991
fDate
1-2 Mar 1991
Firstpage
25
Lastpage
30
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;
fLanguage
English
Publisher
ieee
Conference_Titel
VLSI, 1991. Proceedings., First Great Lakes Symposium on
Conference_Location
Kalamazoo, MI
Print_ISBN
0-8186-2170-2
Type
conf
DOI
10.1109/GLSV.1991.143937
Filename
143937
Link To Document