Layout decomposition method and apparatus for multiple patterning lithography

A method comprising:

• obtaining an initial layout of at least a portion of a given layer of an integrated circuit design from a database;
• splitting each of a plurality of shapes of the layout from the database into multiple segments;
• constructing a constraint graph to represent relationships between the segments, wherein the constructing step comprises constructing the constraint graph as a two-colorable constraint graph in which segment nodes represent respective ones of the segments and a conflict arc between a given pair of the segment nodes indicates that the corresponding segments are from different shapes and are within a specified threshold distance of one another;
• reducing the constraint graph to a stitch graph, wherein the reducing step comprises the step of forming components as respective groups of the segment nodes of the constraint graph such that those segment nodes within a given component of the formed components are connected by conflict arcs and those segment nodes in different components of the formed components are not connected by the conflict arcs;
• determining at least one cut line of the stitch graph;
• and
• generating a decomposed layout based on the determined cut line;
• wherein the obtaining, splitting, constructing, reducing, determining and generating steps are performed by a processing device comprising a processor coupled to a memory;
• and
• wherein the decomposed layout is provided to a lithography system to pattern a wafer based on the decomposed layout.