**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.

(BibTeX -- Citations -- Citations from MIT hypertext bibliography -- CiteSeer (SODA) -- CiteSeer (JGAA))

Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.