edited by M Sarrafzadeh (Northwestern Univ.) & D T Lee (Northwestern Univ.)

In the past two decades, research in VLSI physical design has been directed toward automation of layout process. Since the cost of fabricating a circuit is a fast growing function of the circuit area, circuit layout techniques are developed with an aim to produce layouts with small areas. Other criteria of optimality such as delay and via minimization need to be taken into consideration. This book includes 14 articles that deal with various stages of the VLSI layout problem. It covers topics including partitioning, floorplanning, placement, global routing, detailed routing and layout verification. Some of the chapters are review articles, giving the state-of-the-art of the problems related to timing driven placement, global and detailed routing, and circuit partitioning. The rest of the book contains research articles, giving recent findings of new approaches to the above-mentioned problems. They are all written by leading experts in the field. This book will serve as good references for both researchers and professionals who work in this field.

• Issues in Timing Driven Layout (M Marek-Sadowska)
• Binary Formulations for Placement and Routing Problems (S M Kang & M Sriram)
• A Survey of Parallel Algorithms for VLSI Cell Placement (P Banerjee)
• Approximate Solutions for Graph and Hypergraph Partitioning (F Makedon & S Tragoudas)
• Integer Program Formulations of Global Routing and Placement Problems (T Lengauer and M Lügering)
• Circuit Partitioning Algorithms Based on Geometry Model (T Asano & T Tokuyama)
• The Three-Dimensional Channel Routing Problem (M L Brady et al.)
• On the Manhattan and Knock-Knee Routing Models (D Zhou & F P Preparata)
• Switch-Box Routing Under the Two-Overlap Wiring Model (T F Gonzalez et al.)
• A Note on the Complexity of Stockmeyer's Floorplan Optimization Technique (T-C Wang & D F Wong)
• An Algorithm to Eliminate All Complex Triangles in a Maximal Planar Graph for Use in VLSI Floorplan (S Tsukiyama et al.)
• Constrained Via Minimization and Signed Hypergraph Partitioning (C-J Shi)
• The Virtual Dimensions of a Straight Line Embedding of a Plane Graph (T Takahashi & Y Kajitani)
• Routing Around Two Rectangles to Minimize the Layout Area (T F Gonzalez & S L Lee)