The subgraph isomorphism problem for outerplanar graphs

DOI10.1016/0304-3975(82)90133-5zbMath0522.68061MaRDI QIDQ1056237

Maciej M. Sysło

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90133-5

zbMATH Keywords

outerplanar graphs; NP-complete; planar graph; subgraph isomorphism problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C99: Graph theory

Related Items

The complexity of subgraph isomorphism for classes of partial k-trees, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs, Subgraph isomorphism for biconnected outerplanar graphs in cubic time, Maximum packing for biconnected outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Graphs with forbidden subgraphs
• An Analysis of a Good Algorithm for the Subtree Problem
• Subtree Isomorphism in O(n5/2)