Parallel Algorithms for Planar Graph. Isomorphism and Related Problems.

摘要

Let G = (V,E) be a planar graph embedded in the plane. We assume that the embedding is specified by giving an orientation to G (11). Planar graph isomorphism can be reduced to finding the triconnected components of the two graphs involved, partitioning these components into isomorphism equivalence classes and testing the isomorphism of the corresponding 3- connected trees (8). Since fast parallel algorithms for tree isomorphism are known (11), (2), we concentrate here on the problems of identifying the triconnected components of planar graphs and on testing the isomorphism of triconnected graphs. The latter can be viewed as a special case of the general coarsest partitioning problem (1) which will also be considered in this paper. We present several new efficient parallel algorithms for the above problems. The complexity of these algorithms will be examined in the context of two models of parallel computation: the concurrent-read exclusive-write parallel random access machine (PRAM), and the two dimensional array of processors. We assume in the rest of the paper that the reader is familiar with the basic parallel techniques for both of these models. In addition, some familiarity with graph theory will also be assumed.