Multi-patterning graph reduction and checking flow method

Abstract

A method of generating a plurality of photomasks includes generating a circuit graph. The circuit graph comprises a plurality of vertices and a plurality of edges. Each of the plurality of vertices is representative of one of a plurality of conductive lines. The plurality of edges are representative of a spacing between the conductive lines less than an acceptable minimum distance. Kgraph comprising a first set of vertices selected from the plurality of vertices connected in series by a first set of edges selected from the plurality of edges and having at least one non-series edge connection between a first vertex and a second vertex selected from the first set of vertices is reduced by merging a third vertex into a fourth vertex selected from the first set of the plurality of vertices. An n-pattern conflict check is performed and the photomasks generated based on the result.