MULTILAYER ROUTING METHOD AND STRUCTURE FOR SEMICONDUCTOR INTEGRATED CIRCUIT

A constraint graph is generated by representing plural nets by using vertices and correlation in the horizontal and vertical directions among the nets by using edges. Then, clustering is conducted so that each of the vertices of the constraint graph is assigned to any one of plural layers in view of a channel height and so as to minimize the number of stacked vias. Next, routing topology is obtained on the basis of obtained clusters of the respective layers and the constraint graph, and routing patterns satisfying a design rule are obtained on the basis of the routing topology. In the clustering, the number of the stacked vias is minimized while retaining the minimum channel height in view of the final routing patterns. Accordingly, the routing patterns satisfying a desired design rule can realize a high density, resulting in a compact semiconductor integrated circuit.