  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.
