Wiring Knock-Knee Layouts -- A Global Approach

Frank Wagner (joint work with Majid Sarrafzadeh, Dorothea Wagner) Institut für Informatik, Freie Universität Berlin email: wagner@inf.fu-berlin.de Report B 92-07 March 92

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-07.ps.gz
We present a global approach to solve the three-layer wirability problem for knock-knee layouts. In general, the problem is ${\cal NP}$-complete. Only for very special layouts a polynomial three-layer wiring algorithm is known up to now. In this paper we show that for a large class of layouts the problem can be formulated as a path problem in a special class of graphs or as a two-satisfiability problem and thus may be solved efficiently. Moreover, it is shown that a minimum stretching of the layout into a layout belonging to this class can be found by solving a clique cover problem in an interval graph. This problem is polynomially solvable as well. Altogether, the method also yields a good heuristic to derive three-layer wirability for arbitrary knock-knee layouts.