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
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 O(n). It thus
improves the algorithm in of Formann, Wagner and Wagner
that determines area-optimal layouts with minimum total
wire length in O(n2) time, where the number of bends
is Ω(n2). Moreover, this is the first
area-optimal layout algorithm with linear running time.
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.
