CALL ROUTING AND THE RATCATCHER

Suppose we expect there to be p(ab) phone calls between locations a and b, for all choices of a, b from some set L of locations. We wish to design a network to optimally handle these calls. More precisely, a ''routing tree'' is a tree T with set of leaves L, in which every other vertex has valency 3. It has ''congestion'' < k if for every edge e of T, there are fewer than k calls which will be routed along e, that is, between locations a, b in different components of T\e. Deciding if there is a routing tree with congestion < k is NP-hard, but if the pairs ab with p(ab) > 0 form the edges of a planar graph G, there is an efficient, strongly polynomial algorithm. This is because the problem is equivalent to deciding if a ratcatcher can corner a rat loose in the walls of a house with floor plan G, where p(ab) is a thickness of the wall ab. The ratcatcher carries a noisemaker of power k, and the rat will not move through any wall in which the noise level is too high (determined by the total thickness of the intervening walls between this one and the noisemaker). It follows that branch-width is polynomially computable for planar graphs - that too is NP-hard for general graphs.