Automatic building of graphs rectangularly dualisable for use in IC floorplanning

The author presents an efficient algorithm that transforms an arbitrary graph, representing a custom integrated circuit, into one suitable for rectangular topology generation, via rectangular dualization, for use in a top-down floorplanning. The algorithm makes use of efficient techniques in graph processing such as planar embedding and introduces a novel procedure to transform a tree of biconnected subgraphs into a path. The algorithm offers three options for communication crossover solving, wiring blocks, grouped wiring blocks or passthrough. The grouping option in particular prevents fast increases in the number of writing blocks in the circuits. The algorithm is efficient and is very well suited for interactive applications