Patent ID: 8402396

Claim:
A layout decomposition method to produce exposure layouts for double patterning lithography from an initial layout, the method comprising steps of: accepting an initial double patterning lithography polygonal layout; fracturing features in the polygonal layout into rectangular layout set of non-overlapping rectangular features; constructing a conflict graph over the rectangular features, wherein edges between nodes in the conflict graph identify rectangular features having conflicting edges that are less than predetermined minimum coloring spacing distance and rectangular features having touching edges; conducting node splitting to split rectangular features identified as conflicting according to the conflict graph while extending split rectangles to create an overlay margin between split rectangular features; updating the conflict graph to generate new nodes, identifying irresolvable conflict cycles in the updated conflict graph and deleting edges in the conflict graph associated with the irresolvable conflict cycles; conducting, by using a computer, coloring of the rectangular features to obtain a two-colorable solution for rectangles identified in the updated conflict graph, where a weighted cost of the overlap lengths, number of line-ends and design rule violations is minimized.