Patent Document ID: 8799844
Application ID: 13016033
Patent Status: 1

Claim One:
1. A method comprising: obtaining an initial layout of at least a portion of a given layer of an integrated circuit design from a database; splitting each of a plurality of shapes of the layout from the database into multiple segments; constructing a constraint graph to represent relationships between the segments, wherein the constructing step comprises constructing the constraint graph as a two-colorable constraint graph in which segment nodes represent respective ones of the segments and a conflict arc between a given pair of the segment nodes indicates that the corresponding segments are from different shapes and are within a specified threshold distance of one another; reducing the constraint graph to a stitch graph, wherein the reducing step comprises the step of forming components as respective groups of the segment nodes of the constraint graph such that those segment nodes within a given component of the formed components are connected by conflict arcs and those segment nodes in different components of the formed components are not connected by the conflict arcs; determining at least one cut line of the stitch graph; and generating a decomposed layout based on the determined cut line; wherein the obtaining, splitting, constructing, reducing, determining and generating steps are performed by a processing device comprising a processor coupled to a memory; and wherein the decomposed layout is provided to a lithography system to pattern a wafer based on the decomposed layout.