Parallel algorithms for planar graph isomorphism and related problems
Joseph F. JáJá, S. Rao Kosaraju · IEEE Transactions on Circuits and Systems · 1988
Parallel algorithms for planar graph isomorphism and several related problems are presented. Two models of parallel computation are considered: the CREW-PRAM model and the two-dimensional array of processors. The results include O( square root n)-time mesh algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single-function coarsest partitioning problem.>