A logic-topological calculus for the construction of integrated circuits. II. (Q1096590)

The layout problem of a given planar graph into two layers is considered. A probabilistic algorithm (based on the annealing simulation [\textit{S. Kirkpatrick}, \textit{C. D. Gelatt} and \textit{M. P. Vecchi}, Science 220, 671--680 (1983; Zbl 1225.90162)]) for designing an optimal layout (according to the number of conflicts requiring the crossing to another layer) is presented. This algorithm runs in linear time while the best-known deterministic algorithm runs in \(O(n^ 3)\) time [\textit{F. Hadlock}, SIAM J. Comput. 4, 221--225 (1975; Zbl 0321.05120)]. Several further layout optimization problems (for example, balanced layout) are discussed in order to motivate the reader for further research. For part I see [Informatik, Forsch. Entwickl. 1, 38--47 (1986; Zbl 0617.94013)].