Patent ID: 8312394

Claim:
A method for determining a mandrel mask layout and a trim mask layout for use in a spacer-is-dielectric (SID) self-aligned double-patterning (SADP) process, the method comprising: determining whether a graph corresponding to a design intent is two-colorable, wherein the graph is two-colorable if a two-coloring can be determined for the graph; in response to determining that the graph is not two-colorable, merging one or more pairs of shapes in the design intent to obtain a modified design intent, wherein merging the one or more pairs of shapes involves merging a first shape and a second shape in the design intent into a contiguous shape, and wherein a modified graph corresponding to the modified design intent is two-colorable; determining a two-coloring for the modified graph; placing, by computer, one or more core shapes in the mandrel mask layout which correspond to vertices in the modified graph that are associated with a first color in the two-coloring; and placing, by computer, one or more shapes in the trim mask layout for separating shapes in the design intent that were merged, wherein separating the shapes involves separating the contiguous shape into the first shape and the second shape using the trim mask layout.