A Graph Model and the Embedding of MOS Circuits

The direct automated transformation of a circuit into the "best" physical layout is hard. An alternative is the transformation of a circuit into a suitable intermediate form, the layout topology. Each layout topology defines an equivalence class of physical layouts. A few layout topologies can be chosen according to their likeliness for leading to the "best" design. Each of these layout topologies can then be transformed into a physical layout that will be optimized. The final design can be chosen from the set of optimized physical layouts. Each optimized physical layout corresponds to a unique layout topology. A circuit is modeled as a graph, The circuit's graph model is analyzed by the embedding algorithm. The embedding algorithm determines the set of layout topologies that will be transformed into the physical layouts for further processing. A layout topology is specified as a graph together with the set of cyclic orders of the vertices, and the layer assignment of the edges.