RCC8 Is Polynomial on Networks of Bounded Treewidth

Manuel Bodirsky, Stefan Wölfl

We construct an 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.