Abstract
A graph-theoretical approach for solving the layout problem of a CMOS functional cell is presented. After the transistor pairing the chaining problem is modeled as an abutability graph. The chaining problem is solved by finding a maximum independent set of vertrices in the graph. A method based on Boolean arithmetic is applied to find all the maximal independent sets which correspond to all the optimal chainings. An exhaustive or an improved min-cut algorithm is applied to place the chains. Good layouts have been obtained on benchmark data.