RCC8 Is Polynomial on Networks of Bounded Treewidth

A tree decomposition We construct an homogeneous (and ω-categorical) of a constraint network is a tree decomposition of its constraint representation of the relation algebra RCC8, which graph: roughly speaking, a decomposition defines a is one of the fundamental formalisms for spatial set of subnetworks that can be glued together in a treelike reasoning. As a consequence we obtain that the manner. The width of such a decomposition, then, is the size network consistency problem for RCC8 can be of the largest subnetwork in the decomposition (in terms of solved in polynomial time for networks of bounded the variables in the network).