Method and apparatus for performing routability checking

摘要

Some embodiments of the invention provide a method of determining whether a set of routes can be geometrically embedded in a region according to a particular wiring model. The method identifies a congestion graph that has a set of edges, where at least two edges are neither orthogonal nor parallel. For each edge, the method identifies the set of routes that intersect the edge. It then determines whether any edge is overcongested.