The orientation of modules based on graph decomposition

1 June 1991

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 40 (6) , 774-780
https://doi.org/10.1109/12.90255

Abstract

In the layout stage of VLSI and printed circuit board (PCB) design, after all circuit modules (rectangular) are placed, it is possible to flip the modules so as to reduce the total net length. The authors formulate the orientation of modules as a graph problem and prove it to be NP-complete. The orientation problem is shown to be equivalent to finding a minimum cut of a graph with some arcs of negative capacities. In many cases, the graph can be decomposed into subgraphs to reduce the search space for optimum orientation. Experiments with real cases show that module orientation reduces the total net length and improves the routability.

Keywords

This publication has 4 references indexed in Scilit:

A new approach to the pin assignment problem
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
Automatic Placement A Review of Current Techniques
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1986
Circuit layout
Proceedings of the IEEE, 1981
An Efficient Heuristic Procedure for Partitioning Graphs
Bell System Technical Journal, 1970