Planar graphs also play an important role in colouring problems. In our 'road-map'
graph, let us suppose that Shell, Esso, BP, and Gulf wish to erect five garages between
them, and that for economic reasons no company wishes to erect two garages at neighbouring
corners. Then Shell can build at P, Esso can build at Q, BP can build at S, and
Gulf can build at T, leaving either Shell or Gulf to build at R (see Fig. 1.11). However,
if Gulf backs out of the agreement, then the other three companies cannot erect the
garages in the specified manner.