  We present the first parallel fixed-parameter algorithm for subgraph
isomorphism in planar graphs, bounded-genus graphs, and, more generally, all
minor-closed graphs of locally bounded treewidth. Our randomized low depth
algorithm has a near-linear work dependency on the size of the target graph.
Existing low depth algorithms do not guarantee that the work remains
asymptotically the same for any constant-sized pattern. By using a connection
to certain separating cycles, our subgraph isomorphism algorithm can decide the
vertex connectivity of a planar graph (with high probability) in asymptotically
near-linear work and poly-logarithmic depth. Previously, no sub-quadratic work
and poly-logarithmic depth bound was known in planar graphs (in particular for
distinguishing between four-connected and five-connected planar graphs).
