Subgraph Isomorphism in Planar Graphs and Related Problems
<|reference_start|>Subgraph Isomorphism in Planar Graphs and Related Problems: 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.<|reference_end|>
@article{eppstein1999subgraph,
    title={Subgraph Isomorphism in Planar Graphs and Related Problems},
    author={David Eppstein},
    journal={J. Graph Algorithms & Applications 3(3):1-27, 1999},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9911003},
    primaryClass={cs.DS}
}