Constraint graph (layout)

In some tasks of integrated circuit layout design a necessity arises to optimize placement of non-overlapping objects in the plane.

Constraint graphs capture the restrictions of relative movements of the objects placed in the plane.

These graphs, while sharing common idea, have different definition, depending on a particular design task or its model.

The constraint graph for a given floorplan is a directed graph with vertex set being the set of floorplan blocks and there is an edge from block b1 to b2 (called horizontal constraint), if b1 is completely to the left of b2 and there is an edge from block b1 to b2 (called vertical constraint), if b1 is completely below b2.

In this context, the horizontal constraint graph is the undirected graph with vertex set N and two nets are connected by an edge if and only if horizontal segments of the routing must overlap.