Subgraph Isomorphism in Planar Graphs and Related Problems

1999/01/01 by David Eppstein · 7 citations
Computer Science · Mathematics · Chemistry · #Advanced Graph Theory Research #Optimization and Search Problems #Graph Theory and Algorithms #Induced subgraph isomorphism problem #Subgraph isomorphism problem #Isomorphism (crystallography) #Graph isomorphism #Combinatorics #Planar #Mathematics #Planar graph #Computer science #Discrete mathematics #Graph #Line graph #Crystallography #Chemistry

paper · doi:10.7155/jgaa.00014

openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Abstract

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.

Citations

• On the succinct representation of graphs
• Finding a Minimum Circuit in a Graph
• Linear-time computation of optimal subgraphs of decomposable graphs
• Arboricity and Subgraph Listing Algorithms
• Graph minors. V. Excluding a planar graph
• Diameter and Treewidth in Minor-Closed Graph Families
• The clique problem for planar graphs
• Approximation algorithms for NP-complete problems on planar graphs

Cited by

• Deciding first-order properties of locally tree-decomposable structures
• Grad and classes with bounded expansion II. Algorithmic aspects
• Polynomial algorithms for open plane graph and subgraph isomorphisms
• Linkless and flat embeddings in 3-space and the unknot problem
• Computing the Girth of a Planar Graph in Linear Time
• The Planar Tree Packing Theorem
• Subgraph isomorphism problem [wikipedia]