NECESSARY AND SUFFICIENT CONDITIONS FOR THE ROUTABILITY OF CLASSICAL CHANNELS

This paper studies the solvability of the channel routing problem. Usi ng a simple 'constructive' methodology, we prove which instances of th e 'classical' channel routing problem can bc solved. The set of non-so lvable channels turns out to be remarkably small. Many existing channe l routers, however, fail on channels which may be complicated, but whi ch are now proven to bc solvable. Although this result is mainly theor etical, the concepts and insights of the proof can be mapped directly into a very practical channel routing algorithm. This algorithm always finds a solution, whenever one exists. A multiple-layer gridless chan nel router was implemented using our concepts. It turned out to bc ver y competitive, on benchmark channels as well as on real-life circuits.