Next: Acknowledgements Up: COLORING MAPS AND Previous: REALIZING THE REDUCTION ALGORITHM

# REALIZING THE KEMPE TRANSFORMATION ALGORITHM

Realizing the Kempe transformation algorithm as control of the Pereira-Porto logic presents a more difficult challenge to the designers of control languages for logic programming. Of course, the postponement part of the algorithm is the same as before; the difficulty comes when it is necessary to color a country with four differently colored neighbors.

The first step is to identify opposite neighbors of the four neighbor country. This depends not merely on the fact that the map is planar but on the actual imbedding in the plane. This information has been discarded when the map is represented as a graph. If the graph is described by giving for each country a list of its neighbors, the imbedding information can be including by listing the neighbors in cyclic order -- clockwise or counterclockwise. Otherwise, it can be restored in general only with difficulty. Figure 3 shows cases where this isn't trivial. Of course, we can modify the algorithm to try every pair of vertices to see if they are unconnected by a path of their two colors. The above argument shows that this is guaranteed to succeeed but presumably at somewhat greater cost than if the cyclic order is known.

Figure 3.

Looking for a changeable country is a process of search whereby only certain values are allowed for certain variables and goals that become unsatisfied are re-satisfied by changing only certain variables in certain ways. A good control system for logic programs should permit the expression of such strategies.

John McCarthy
Sat Feb 22 18:04:49 PDT 1997