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.