Affiliation: | a School of High-Technology for Human Welfare, Tokai University, 317 Nishino, Numazu 410-03, Japan b Department of I.R.O., Universite de Montreal, C. P. 6128, Succ. Centre-ville, Montreal, Canada |
Abstract: | Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19]. |