Patent ID: 8086987

Claim:
A method for providing routes between terminals of a net via a topological routing phase and a geometric routing phase, the method comprising: executing the topological routing phase prior to executing the geometric routing phase, the topological routing phase including: tessellating a routing space by a first plurality of arcs, each of said arcs extending between a corresponding pair of nodes each indicative of a corresponding one of the terminals; routing in said routing space a topological graph of the net; performing a plurality of occupancy reducing actions on a portion of said topological graph containing an arc having an occupancy greater than a predetermined threshold, each of said occupancy reducing actions performing operations distinct from remaining ones of said plurality of occupancy reducing actions; and, modifying said topological graph to incorporate topological differences between an occupancy reduced portion of said topological graph resultant from at least one of said occupancy reducing actions and said portion of said topological graph; and, executing said geometric path routing phase to route said geometric arrangement of the net in accordance with said topological graph.