Building Rectangular Floorplans–A Graph Theoretical Approach

Rectangular dualisation is a technique used to generate rectangular topologies for use in top-down floorplanningof integrated circuits. In order for this technique to be used in a floorplanning system, its input, the connectivitygraph representing an integrated circuit has to fulfill a number of conditions. This paper presents an efficientalgorithm that transforms an arbitrary connected graph, representing an integrated circuit, into another graphthat is guaranteed to fulfill these conditions and to admit rectangular duals. Effectively, the algorithm solves theglobal routing problem by using three techniques: passthrough, wiring blocks and collapsed wiring blocks. Resultingfloorplans may be passed to a chip assembler and detailed router package to complete the layout. This paper alsointroduces a novel technique to transform a tree of biconnected sub-graphs into a block neighbourhood graphthat is a path