RCC8 is polynomial on networks of bounded treewidth
Manuel Bodirsky, Stefan Wölfl · 2011
We construct an homogeneous (and ω-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.