Mathematical models for the circuit layout problem

[摘要] In the first part of this paper the basic differences between the classical (placement, routing) and the topological approach to solving the circuit layout problem are outlined. After a brief survey of some existing mathematical models for the problem, 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.

[学科分类] 计算机科学（综合）