Parallel Algorithms for Planar Graph Isomorphism and Related Problems.

Abstract

We present new efficient parallel algorithms for planar graph isomorphism and several related problems. Our main parallel model is the SQRT n x SQRT n mesh of processors, where n is the length of the input. Our results include O(SQRT n) time algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single function coarsest partitioning problem.