Patent ID: 8677297

Claim:
A method for checking a set of multi-patterning layout design rules on a region of an integrated circuit layout, the layout including a plurality of islands, for use by a computer system having access to a design rule data set indicating values for multi-patterning spacing constraints among islands in a particular layer, the method comprising the steps of: the computer system iteratively building a data structure identifying the plurality of islands and a plurality of relationships among respective pairs of the islands, each of the relationships indicating that the pair of islands related by the relationship violates one of the multi-patterning spacing constraints; during the step of building a data structure, and before all of the relationships are included in the data structure, in dependence upon the relationships that are included in the data structure, detecting a multi-patterning coloring violation among islands represented in the data structure; and reporting the multi-patterning coloring violation to a user.