Combinatorial Algorithms for Integrated Circuit Layout

The explosive growth of integrated circuitry has created a need for a one-stop reference source that combines practical with theoretical aspects of the subject. This work takes a major step in this direction by offering a unified compilation that will be useful for both practitioners and theoreticians interested in circuit layout. It presents an overview of what are currently the most important combinatorial problems in circuit layout and describes their solutions. Discussions cover algorithms currently used in layout systems, as well as some new algorithmic developments that hold promise of stimulating the improvement of layout systems in the future.