Constraint graph

In constraint satisfaction research of artificial intelligence and operations research, the primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graph whose nodes are the variables of the problem and an edge joins a pair of variables if the two variables occur together in a constraint.

The primal graph of a constraint satisfaction problem can also be defined as the primal graph of the hypergraph made of the variables and the constraint scopes. In the case of binary constraint network any two nodes having missing arcs between each other means these two nodes have the universal binary relation between each pair of values.