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(n2) time, where the
number of bends is Ω(n2). 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.
