Patent Document ID: 20100229145
Application ID: 12397321
Patent Status: 0

Claim One:
1. A method of segmenting a circuit layout design, comprising; designating separated edges in layout design data that should be imaged by separate lithographic masks; generating cut paths to cut one or more polygons in the layout design data into a plurality of polygon segments; constructing a conflict graph, such that each polygon segment is represented by a node in the conflict graph, nodes representing polygon segments that have separated edges are connected by a separation edge, each generated cut path is represented by a cut path edge, and nodes representing abutting polygon segments are connected by a corresponding cut path edge; constructing a dual graph for the conflict graph, such that the dual graph contains dual graph separation edges corresponding to the separation edges of the conflict graph, and the dual graph contains dual graph cut path edges corresponding to the cut path edges of the conflict graph; selecting dual graph cut edges in the dual graph by identifying nodes in the dual graph having an odd number of incident dual graph separation edges, and determining the dual graph cut path edges that make up the dual graph cut path edge minimum-weight T-join of the identified nodes; and adding the cut paths represented by the selected dual graph cut path edges to the layout design data.