Triple-pattern lithography layout decomposition

A method for decomposing a layout for triple-pattern lithography, said method comprising:

• generating a conflict graph from a layout of a device level of a semiconductor device, said conflict graph including a plurality of nodes, each said node representing a polygon of said layout, and a plurality of links, each connecting two of said nodes, each said link corresponding to a distance between adjacent polygons being less than a minimum separation distance using a single photomask;
• converting said conflict graph to a simplified conflict graph;
• and
• analyzing said simplified conflict graph and applying at least one rule to said simplified conflict graph to determine if said layout is decomposable into three photomasks,
• wherein at least one of said generating, converting and analyzing is carried out by a computer.

A non-transitory machine readable storage medium encoded with computer program code, such that when the computer program code is executed by a processor, the processor performs a method comprising:

• generating a conflict graph from a layout for a device level of a semiconductor device, said conflict graph including a plurality of nodes, each said node representing a polygon of said layout and a plurality of links connecting two said nodes, each said link corresponding to a distance between adjacent polygons being less than a minimum separation distance using a single photomask;
• and
• converting said conflict graph to a simplified conflict graph, said converting including at least one of a) removing one or more of said nodes from said conflict graph that are connected to two or fewer of said links and b) partitioning portions of said conflict graph connected by a single link of said links,
• wherein at least one of said generating and converting is carried out by a computer.