- Subgraph isomorphism in planar graphs and related problems.
D. Eppstein.
Tech. Rep. 94-25, ICS, UCI, 1994.
6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632–640.
arXiv:cs.DS/9911003.
J. Graph Algorithms and Applications 3 (3): 1–27, 1999.Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.