•A DISTRIBUTED SHORTEST PATH ALGORITHM FOR A PLANAR NETWORK'

An algorithm is presemed for finding a single source shortest path tree in a planar undirected distributed network with nonnegative edge COSlS. The number of messages used by the algorithm is 0 (n 513) on an n-node network. ' Distributed algo-rithms are also presemed for finding a breadth-first spanning tree in a general network, for finding a shortest path tree in a general network, for finding a separaEOr of a planar network, and for finding a division of a planar network. Key words and phrases. breadth-first search, disaibuted network, message complex-ity, planar network, planar separator, single source shortest padls. Consider a problem in which the information necessary for its solution is distri-buted among the nodes of a network. A fundamental question in distributed computa-tion is how [0 solve the problem, llSing a minimum number of messages [0 route the information. In particular, suppose that the problem is a graph problem abom the net