US Patent 9679095 Layout decomposition for multiple patterning lithography

Aspects of the disclosed techniques relate to techniques of layout decomposition for multiple patterning lithography. Data of a coloring graph are derived from layout data for a layout design. The coloring graph is simplified by repeatedly applying a plurality of graph simplification units. Each of the graph simplification units is configured to use a unique approach to simplify a graph. Based on the simplified coloring graph, the layout design is decomposed to generate decomposition information. The decomposition process may comprise applying a heuristic method for coloring if needed. The decomposition information may comprise information of one or more layout regions that cannot be decomposed.