Graph analysis for double pattern lithography is described. Layout shapes are decomposed into rectangles and a vertex is provided for each rectangle. Double pattern spacing conflicts are determined and shown as edges for the graph analysis. Odd cycles are used to identify double pattern lithography violations. Cycles can be completed with the addition of edges between vertices where stitches have been included in the layout. Edges between touching shapes do not count toward the odd count in the cycles. Fixes are included by increasing space or by rerouting. A portion of the layout can be incrementally changed and a local update of the graph analysis performed. Correct by construction layout is implemented by avoiding certain odd cycle prone layout routings.