Patent ID: 7464358

Claim:
A method for routing interconnection paths between terminals via a routing procedure comprising: executing a topological routing phase prior to executing a geometric routing phase; executing in said topological routing phase a plurality of topological transformations on a routed topological graph indicative of a geometric arrangement of the terminals, said plurality of topological transformations each operably distinct one from another; and, executing said geometric routing phase to route the interconnection paths in said geometric arrangement of the terminals in accordance with said topological graph; where said executing of said topological transformations includes: determining if an overload condition exists in said topological graph and responsive to a positive determination thereof performing: creating a local topological graph corresponding to a portion of said routed topological graph containing said overload condition; transforming said local topological graph into a set of transformed candidate graphs by executing said plurality of topological transformations; selecting one of said transformed candidate graphs in accordance with a first predetermined criterion; and, modifying said topological graph to incorporate topological differences between said selected one of said transformed candidate graphs and said topological graph.