Layout Decomposition For Triple Patterning Lithography

A method, comprising:

• with a computer,
• receiving layout data for a layout design, the layout design corresponding to at least a portion of an integrated circuit, the layout data comprising mask assignment information for some layout features;
• deriving data of a coloring graph from the layout data, the coloring graph comprising vertices representing layout features in the layout design and edges between some pairs of vertices indicating the mask assignment information;
• performing a graph reduction process and a graph partitioning process on the coloring graph to generate a simplified coloring graph, wherein the graph partitioning process comprises separating biconnected components;
• decomposing the layout design based on the simplified coloring graph to generate decomposition information;
• and
• storing the decomposition information.

A system comprising:

• one or more processors, the one or more processors programmed to perform a method, the method comprising:
• receiving layout data for a layout design, the layout design corresponding to at least a portion of an integrated circuit, the layout data comprising mask assignment information for some layout features;
• deriving data of a coloring graph from the layout data, the coloring graph comprising vertices representing layout features in the layout design and edges between some pairs of vertices indicating the mask assignment information;
• performing a graph reduction process and a graph partitioning process on the coloring graph to generate a simplified coloring graph, wherein the graph partitioning process comprises separating biconnected components;
• decomposing the layout design based on the simplified coloring graph to generate decomposition information;
• and
• storing the decomposition information.