1. A method comprising: obtaining an initial layout of at least a portion of a given layer of an integrated circuit design; splitting each of a plurality of shapes of the layout into multiple segments; constructing a constraint graph to represent relationships between the segments; reducing the constraint graph to a stitch graph; 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.