Patent ID: 8468470

Claim:
A method comprising: (a) receiving data representing a layout of a double patterned (DPT)-layer of an integrated circuit generated by a place and route tool implemented by a processor, the layout including a plurality of polygons to be formed in the DPT-layer by a multi-patterning process; (b) receiving at least one identification of a subset of the plurality of polygons that are to be formed in the DPT-layer using the same photomask as each other; (c) constructing a graph of the subset of the plurality of polygons and any intervening polygons of the plurality of polygons, wherein the subset of the plurality of polygons includes at least two polygons unconnected to each other within the DPT layer and having a non-zero unpatterned space therebetween, the at least two polygons represented in the graph by a single node, the graph including connections connecting adjacent ones of the nodes in the graph that are positioned within a threshold distance of each other; and (d) identifying a multi-patterning conflict if any subset of the connections form an odd loop.