Incremental multi-patterning validation

A computer system operative to:

• receive a multi-patterning layer of a design in a memory of the computer when the computer is invoked to validate the design, wherein the multi-patterning layer includes a first error in a first shape of the multi-patterning layer;
• correct the first error in accordance with a first rule thereby forming a corrected layer;
• incrementally validate a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer, wherein the first portion includes the corrected first shape, wherein the first graph includes the first connected component, wherein the first portion is associated with the first connected component
• form a second graph including the first connected component and a second connected component different from the first connected component;
• select the first portion of the corrected layer;
• and
• validate the selected first portion of the corrected layer without validating a second portion of the corrected layer associated with the second connected component.

A non-transitory computer-readable storage medium comprising instructions, which when executed by a computer, cause the computer to:

• receive a multi-patterning layer of a design in a memory of the computer when the computer is invoked to validate the design, wherein the multi-patterning layer includes a first error in a first shape of the multi-patterning layer;
• correct the first error in accordance with a first rule thereby forming a corrected layer;
• incrementally validate a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer, wherein the first portion includes the corrected first shape, wherein the first graph includes the first connected component, wherein the first portion is associated with the first connected component;
• form a second graph including the first connected component and a second connected component different from the first connected component;
• select the first portion of the corrected layer;
• and
• validate the selected first portion of the corrected layer without validating a second portion of the corrected layer associated with the second connected component.