A Kuratowski constraint is a linear programming inequality used in integer programming formulations
of the graph crossing number. Let 
be a subgraph of a graph 
that is a graph
subdivision of the pentatope graph 
or the utility graph 
. For each pair 
of graph edges of 
, set 
when 
and 
cross and 
otherwise. Let 
consist of the pairs for which 
and 
lie on graph paths replacing
two nonadjacent graph edges of 
or 
. Since 
is a nonplanar graph, Kuratowski's theorem implies that at least one
such pair must cross, giving the inequality
 |
The phrase "Kuratowski subdivision constraint" specifies the case in which 
contains subdivision vertices rather than being exactly
or 
(Chimani et al. 2008, Chimani 2011). Chimani (2011) proved that several classes
of these constraints define facets of the associated polytope.
