Mathematical models for the circuit layout problem

In this paper mathematical models for use in a topological approach to solving the circuit layout problem are outlined. After a brief survey of some existing models, an improved model is suggested. This model is based on the concept of partially oriented graph and contains more topological information than earlier models. This reduces the need for special constraints on the graph embedding algorithm. The models also allow pin and gate assignment in function of the layout under certain conditions.