WIRING KNOCK-KNEE LAYOUTS - A GLOBAL APPROACH

We present a global approach to solve the three-layer wirability probl em for knock-knee layouts. In general, the problem is NP-complete. Onl y for very restricted classes of layouts polynomial three-layer wiring algorithms are known up to now. In this paper we show that for a larg e class of layouts a three-layer wiring can be constructed by solving a path problem in a special class of graphs or a two-satisfiability pr oblem, and thus may be wired in time linear in the size of the layout area. Moreover, it is shown that a minimum stretching of the layout in to a layout belonging to this class can be found by solving a clique c over problem in an interval graph. This problem is solvable in time li near in the size of the layout area as well. Altogether, the method al so yields a good heuristic for the three-layer wirability problem for knock-knee layouts.