Three Layers Are Enough

In this paper we show that any channel routing problem of density d involving two-terminal nets can always be solved in the knock-knee mode in a channel of width equal the density d with three conducting layers. An algorithm is described which produces a layout of n nets with the following properties: (i) it has minimal width d; (ii) it can be realized with three layers; (iii) it has at most 3n vias; (iv) any two wires share at most four grid points.

Authors

• Franco P. Preparata
• Witold Lipski Jr.

Keywords

• Wire
• Routing
• Wiring
• Circuits
• Terminology
• Computer science
• Very large scale integration
• Joining processes
• Grid Points
• Layout Optimization
• Diagonal
• Line Scan
• Set Membership
• Acute Angle
• Algorithm Execution
• Layout Algorithm
• Unit Square
• Horizontal Segment
• Vertical Segments