Patent ID: 8516402

Claim:
A non-transitory machine readable medium storing a program for resolving a design rule violation in a circuit design layout including a plurality of shapes, the program comprising sets of instructions for: identifying a double patterning loop formed by a set of shapes in the design layout, the double patterning loop representing a design rule violation; identifying critical portions of the set of shapes, wherein a critical portion is a portion of a shape that is within a threshold distance from another shape; assigning the critical portions of the set of shapes to a plurality of masks in a manner that reduces a number of cut graphs to be inserted in each shape of the set of shapes, the cut graphs for partitioning the shape into a plurality of segments so that at least two different segments of the shape are assignable to two different masks; inserting cut graphs into the design layout based on the assignment of the critical portions of the set of shapes to the plurality of masks; partitioning the shapes based on the inserted cut graphs; and assigning, for each partitioned shape, at least two different partitions to two different masks, in order to resolve the design rule violation due to the double patterning loop.