A new approach to wiring layouts
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 10 (11) , 1392-1400
- https://doi.org/10.1109/43.97618
Abstract
The author introduces a technique for wiring knock-knee layouts, without using two-colorable maps. This technique can be easily adapted to wire layouts on any type of grid, something that is rather complicated if one uses two-colorable maps. The author presents an algorithm for wiring a given layout in the square grid that uses at most four layers, and produces a two-layer wiring for a given layout, if such a wiring exists. The algorithm runs in time linear with respect to the area occupied by the layoutKeywords
This publication has 10 references indexed in Scilit:
- Techniques for wiring in non-square gridsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Improved techniques for wiring layouts in the square gridPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A linear-time algorithm for routing in a convex gridIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- Stretching and three-layer wiring planar layoutsIntegration, 1989
- Routing through a generalized switchboxJournal of Algorithms, 1986
- A unified approach to layout wirabilityTheory of Computing Systems, 1986
- Routing through a rectangleJournal of the ACM, 1986
- A Linear-Time Routing Algorithm for Convex GridsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- Optimal Three-Layer Channel RoutingIEEE Transactions on Computers, 1984
- Disjoint paths in a rectilinear gridCombinatorica, 1982