On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs

AbstractWe consider the problems of subgraph homeomorphism with fixed pattern, disjoint connecting paths with bounded number of terminal pairs, recognition, and subgraph isomorphism for some classes of planar graphs. Following the results of Robertson and Seymour on forbidden minor characterization, we show that the first three of the above problems for any family of planar graphs closed under minor taking are in NC3 (i.e. they can be solved by an algorithm running in time O(log3 n) using polynomial number of processors). We also show that the related subgraph isomorphism problem for two-connected outerplanar graphs is in NC3. This is the first example of a restriction of subgraph isomorphism to a non-trivial graph family admitting an NC algorithm