An Efficient Graph Theoretic Algorithm for Channel Routing in VLSI Design with Given Constraint Graph

In VLSI design, the channel routing is one of the most significant detailed routings. Given a channel with length in 2-layer Manhattan model. Given a channel with length in 2-layer Manhattan model, Szeszler proved that the width (number of tracks required for routing) of the channel is at most 7/4, and this upper bound can be achieved by a linear time algorithm. In this paper, the channel with horizontal constraint graph is considered as a path. An efficient graph theoretic algorithm is presented, compared with the latest results, our algorithm yields a better bound on the width of the channel.