A Graph Theoretic Approach for 2-layer Channel Routing Problem

摘要

Channel routing in the 2-layer Manhattan model is one of the most investigated problems in VLSI design. David Szeszler 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, we give a linear time algorithm with graph theoretic approach.