Multi-patterning graph reduction and checking flow method

A method, comprising:

• receiving a circuit layout comprising a plurality of conductive lines;
• generating a circuit graph representative of the circuit layout, wherein the circuit graph comprises a plurality of vertices and a plurality of edges, wherein each of the plurality of vertices represents one of the plurality of conductive lines, and wherein each of the plurality of edges is representative of a spacing between the conductive lines less than an acceptable minimum distance;
• coloring the circuit graph with n colors where n is equal to any integer greater than 3, and wherein each of the plurality of vertices is assigned one of the n colors based on an n-patterning checking process including at least one circuit graph reduction, wherein the at least one circuit graph reduction comprises reducing the circuit graph by combining a first vertex of the circuit graph with a second vertex of the graph not directly connected to the first vertex, wherein the first vertex represents a first conductive line of the circuit layout and the second vertex represents a second conductive line of the circuit layout;
• assigning each of the plurality of conductive lines to one of n photomasks based on a color of a corresponding vertex from the plurality of vertices;
• and
• forming the n photomasks for use in a n-patterning photolithographic process.

A system configured to generate a plurality of photomasks, the system comprising:

• a computer configured to:
• receive a circuit layout comprising a plurality of conductive lines;
• generate a circuit graph representative of the circuit layout;
• reduce the circuit graph by combining a first vertex of the circuit graph with a second vertex of the graph not directly connected to the first vertex, wherein the first vertex represents a first conductive line of the circuit layout and the second vertex represents a second conductive line of the circuit layout;
• and
• check the reduced circuit graph for one or more triple patterning conflicts, wherein the checking assigns one of three colors to each of the set of vertices in the reduced circuit graph;
• and
• a photomask generator configured to generate a first photomask, a second photomask, and a third photomask each corresponding to a respective one of the three colors.