An incremental wiring algorithm for VLSI layout design

One of the difficulties in routing problem is in wirability which is to guarantee a physical connection of a given topological route. Wirability often fails since the width of a wire is relatively large compared with the size of modules. As a possible solution, this paper proposes an incremental wiring algorithm which generates wires net-by-net without overlapping other pre-placed circuit elements. The idea is to divide a wire into a series of rectangles and handles them as modules with additional constraints to keep the shape of the wire. The algorithm was implemented and experimented on a small instance to show its promising performance.