---
title: "RCC8 Is Polynomial on Networks of Bounded Treewidth"
authors:
  - "Manuel Bodirsky"
  - "Stefan Wölfl"
doi: "10.5591/978-1-57735-516-8/IJCAI11-133"
url: "https://ijcai.org/proceedings/2011/133"
pdf: "https://ijcai.org/proceedings/2011/0133.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "756-760"
track: ""
keywords:
---

# RCC8 Is Polynomial on Networks of Bounded Treewidth

Manuel Bodirsky, Stefan Wölfl

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 756-760. DOI: [10.5591/978-1-57735-516-8/IJCAI11-133](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-133)

## Abstract

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.