We solve the subgraph isomorphism problem in planar graphs in linear time, for any pattern of constant size. Our results are based on a technique of partitioning the planar graph into pieces of small tree-width, and applying dynamic programming within each piece. The same methods can be used to solve other planar graph problems including connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths.
Recently we were able to characterize the graphs that can occur at most @math times as a subgraph isomorph in an @math -vertex planar graph: they are exactly the 3-connected planar graphs @cite_41 . However our proof does not lead to an efficient algorithm for 3-connected planar subgraph isomorphism. In this paper we use different techniques which do not depend on high-order connectivity.
@cite_41
2074992286
It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) times as a subgraph of the Kb,c-free graphs, b ≥ c and c ≤ 4, iff G is c-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.