A Polynomial time Algorithm for 2-layer Channel Routing Problem

Abstract

Channel routing in the 2-layer Manhattan model is one of the most investigated problems in VLSI design. Dávid Szeszlér [Szeszlér D., A New Algorithm for 2-layer, Manhattan Channel Routing, Proc. 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2003), 179–185] gave a complete characterization of all specifications that are solvable and present a linear time algorithm to solve these specifications with a width at most constant times the length of the problem. In this paper an efficient graph theoretic algorithm for a particular 2-layer Manhattan channel routing problem has been presented, we give a new polynomial time algorithm to solve these specifications with a width better than the result of Dávid Szeszlér.