Multilayer Channel Router for Nonrectangular Channels

摘要

An algorithm for routing multilayer channels whose borders may be irregular and contain connection points in all layers and at every grid position is presented. No restrictions are posed on the wiring in different layers. The routing algorithm opens the way to solve general three dimensional routing problems. The method incorporates a range of strategies which handle connection problems of different complexity. In most (practical) situations a straightforward and fast algorithm is employed. However, as the density of terminals at the borders increases, more complex strategies are required. In the extreme case, which is only of theoretical interest, a solution can even be found if at each channel side all but two grid positions are occupied by terminals.