This paper deals with the layer assignment problem (i.e., the determination of the layers which are going to be used for wiring the signal nets). The problem is first presented and then a solution for two layers is given using only the contact minimization criterion.

Starting from “a layout graph,” the feasibility of the layer assignment is reduced to a coloring problem. The optimization factor is mainly the minimization of the contact number; therefore, the assignment has to induce a minimum amount of color switchings. This is done on a residue weighted graph, by a max-cut algorithm. This algorithm is shown to be polynomial.

Some extensions concern the layer assignment problem in the general case where the minimization takes into account electric performances. Some open problems are discussed.