@techreport{Report-318-1992,
Title = {Optimal Routing Through Dense Channels},
Author = {Dorothea Wagner},
Pages = {269-289},
Year = {1992},
Journal = {International Journal of Computational Geometry \& Applications, 1993},
Volume = {3},
Number = {318},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {We present a new channel routing algorithm in the knock-knee mode that produces for dense problems area-optimal layouts with minimum total wire length and $\cal O(n)$ bends ($n$ number of nets), where the total number of bends is at most $d-2$ ($d$ density) more than the minimum. The running time is $\cal O(n)$. It thus improves the best previously known algorithm, which determines area-optimal layouts with minimum total wire length in $\cal O(n^2)$ time, where the number of bends is $\Omega(n^2)$. Moreover, the algorithm can be modified so as to guarantee three-layer wirable layouts, where the total wire length is at most $n-2$ more than the minimum. The approach we use is completely different from all previously known algorithms. It is based on the notion of cycle graphs introduced in this paper.}
}