  We consider quantifier-free spatial logics, designed for qualitative spatial
representation and reasoning in AI, and extend them with the means to represent
topological connectedness of regions and restrict the number of their connected
components. We investigate the computational complexity of these logics and
show that the connectedness constraints can increase complexity from NP to
PSpace, ExpTime and, if component counting is allowed, to NExpTime.
