Placement Constraint Method for Multiple Patterning of Cell-Based Chip Design

A method, comprising:

• receiving a layout pattern comprising spaced apart cells with features therein;
• constructing a graph representation of the layout pattern;
• identifying closed loops in the graph representation;
• identifying the cells in each of the identified closed loops;
• forming a new layout pattern by relocating a cell from the identified cells in the identified closed loops so that a distance between the identified cells in the identified closed loops is greater than a minimum spacing;
• and
• outputting the new layout pattern to a machine readable storage medium.

A method, comprising:

• receiving a layout pattern, wherein the layout pattern comprises cells with features corresponding to contacts in a middle-of-line (MOL) layer;
• constructing a graph representation of the layout pattern, wherein the graph representation comprises vertices corresponding to the features in the cells and connect lines between the features;
• inspecting the graph representation to identify a closed loop;
• identifying the cells forming the closed loop;
• modifying the layout pattern by relocating one or more cells forming the closed loop so that a distance between non-relocated cells and the one or more relocated cells in the closed loop is greater than a minimum color spacing value;
• outputting the modified layout pattern to a machine readable storage medium.