Path search on rectangular floorplan

Wiring among rectangular blocks is an important component in hierarchical layout. This paper presents algorithms for path search on rectangular floorplan. A fast Steiner tree algorithm of linear complexity is proposed based on a new heuristic of converging search. Taking into account the positional distribution of terminals on the floorplan, it finds the subconnections for each terminal simultaneously and in an order independent manner this often yields global optimum connection of terminals. Experimental results show that the new algorithm out-performs other popular sequential methods for the problem at hand in most cases