Technical Report 317-1992

Title

Wiring Knock-Knee Layouts: A Global Approach

Authors

Majid Sarrafzadeh, Dorothea Wagner, Frank Wagner, and Karsten Weihe

Publication

Lecture Notes in Computer Science 650, Proc. of Third International Symposium on Algorithms and Computation 92, (ISAAC'92), ed. T. Ibaraki, Y. Inagaki, K. Iwama, T. Nishizeki and M. Yamashita, 1992, pp. 388-399

Journal version in IEEE Transactions on Computers 43 (1994), pp. 581-589.

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

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.