Wiring layouts in the tri-hexagonal grid^∗

^∗Research supported in part by the Texas Advanced Research Program under Grant No. 3972 and by a UTD Research Initiation Grant

Abstract

The problem of wiring (or layer assignment for) VLSI layouts is a fundamental and classical one, and arises naturally after the routing phase of a CAD system. In this paper we present an algorithm for wiring layouts in the tri-hexagonal grid. This is the first wiring algorithm for layouts in the tri-hexagonal grid and it produces wirings that require at most five layers. Furthermore, our algorithm runs in O(N) time, where N is the number of grid points occupied by the layout.

Keywords:

• VlSI layout
• wiring
• layer assignment
• tri-hexagonal grid

C.R. Categories:

• F.2
• G.2
• J.6

^∗Research supported in part by the Texas Advanced Research Program under Grant No. 3972 and by a UTD Research Initiation Grant

^∗Research supported in part by the Texas Advanced Research Program under Grant No. 3972 and by a UTD Research Initiation Grant

Notes

^∗Research supported in part by the Texas Advanced Research Program under Grant No. 3972 and by a UTD Research Initiation Grant