
## Algorithm M99-Consistency

INPUT: A constraint network T on M99 OUTPUT: Yes if T has a solution formed by spatial regions of R2
, no if not.

1. Translate T into the generator set as in Lemma 5 2. Look for cycles labelled by - and at most one ./

3. Check whether edges between two vertices in one cycle are not labelled by 6 otherwise return no.

4. Substitute vertices of the cycle with one vertex.

2. If there are more cycles go to Step 2., otherwise return yes.

Figure 7: Algorithm M99-consistency connected components is a O e problem where e is the number of edges in the network.

The 	99 implementation adds, in the worst case, O e 0 edges, where e 0 is the number of edges in T and therefore the number of edges in 	99 T is O(2  e 0

), which is O n2
).

An immediate consequence of Theorem is the following theorem:

Theorem 6 MSAT(M99 is polynomial.

The subalgebras of MC-4 included in M99 are in Table 10 of Appendix A.

## 4.3 The Maximal Tractable Subclass M81

The problem of deciding the consistency of a network of constraints on MC-4 is tractable, by means of Tables 6, 7, and 10 for 85 subalgebras. The remainder is formed by 17 subalgebras, each of these can be either tractable or intractable. The set M81 f CG CGPP CGPP1fCG; CGPPg fCG; CGPP1g fCGPP; CGPP1g fCG; CGPP; CGPP1g fCGPP; CGPP1; CNOg >g contains all these subalgebras, so that if M81 is tractable all these algebras are as well.

By analogy with the schema of the previous section we look for a small generator set for M81 This is G81 ffCG; CGPPg fCG; CGPP; CGPP1g fCGPP; CGPP1; CNOgg The following lemma states the properties of M81 with respect to G81 Lemma 7 Gd 81 M81.

## Proof

The following expressions represent valid implementations of relations in M81 using only elements of G81 and the operators of composition, intersection and converse.