Patent ID: 7945870

Claim:
A processor executed method for detecting hotspots in a circuit layout, comprising: constructing a layout graph G=(V, Ec∪Ep) from the circuit layout where V represents nodes, Ec represents corner edges and Ep represents proximity edges; converting said layout graph to a corresponding dual graph G D =(V D , E D ∪E D ); and iteratively selecting edges and nodes having weights greater than a predetermined threshold value at each iteration as hotspots, wherein said construction of said layout graph G=(V, Ec∪Ep) comprises: creating the nodes ν∈V in a select location of each horizontal or vertical line; for two orthogonally connected lines, connecting two corresponding nodes with the corner edges c∈Ec having a constant weight; creating proximity edges e∈Ep between two closely proximate lines having the same direction, said proximity edges having weights generated from a closed-form formula based weighting scheme.