Hexagonal Models for Channel Routing

In this paper we present new diagonal routing models based on the hexagonal grid, and investigate the potential of these models in terms of channel routing. The hexagonal grid consists of vertical columns, and positive and negative diagonal tracks with slopes and , respectively. The layout geometry of this grid is examined and shown to be compatible with VLSI implementation. Furthermore, this investigation demonstrates some advantages of routing on the hexagonal grid. For a channel routing problem (CRP) having maximum net span s ^* , we give an algorithm which routes any two-sided (two-terminal or multiterminal) net CRP in width in three reserved layers. For densities , this channel width is less than the lower bound of d for routing on the square grid in three nonreserved layers. For CRPs of large span, we show how a previous square grid algorithm can be adapted to the hexagonal grid to obtain three layer routings of width for two-terminal nets and for multiterminal nets. Received November 4, 1994; revised August 7, 1995.