Patent ID: 8484607

Claim:
A method, performed on a computing device having at least one processing unit, that decomposes a layout for triple patterning lithography, comprising: using the at least one processing unit of the computing device to perform actions comprising: receiving the layout with pattern features in the layout specified as shapes; building a triple patterning conflict graph that represents the shapes in the layout and coloring constraints associated with the shapes, wherein the triple patterning conflict graph includes a plurality of nodes each representing a plurality of shapes in the layout, conflict arcs coupled to nodes that have color conflicts that arise when the shapes represented by the nodes are assigned to the same color, and stitch arcs coupled to nodes that represent shapes stitched together; decomposing the shapes represented by the triple patterning conflict graph into three colors to avoid color conflicts while balancing color density among the three colors and minimizing a number of stitches used to represent the shapes in the layout; determining whether the decomposition of the shapes into the three colors results in a color conflict; and in response to determining that there is a color conflict in the decomposition, selectively segmenting the shapes in the decomposition that are associated with the color conflict in order to resolve the conflict.