RCC8 is polynomial on networks of bounded treewidth
Manuel Bodirsky and Stefan Woelfl
We construct an ultra-homogeneous (and omega-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.