The subgraph isomorphism problem for outerplanar graphs
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that SUBOUTISOM remains NP-complete even when the strongest connectivity requirements are imposed on both graphs, except the case when both graphs arc 2-connected.
Abstract
This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity requirements are imposed on both graphs. The same results holds for the induced subgraph isomorphism problem for outerplanar graphs except the case when both graphs are 2-connected; for such graphs we give a polynomial algorithm which verifies whether a 2-connected outerplanar graph is an induced subgraph of another 2-connected outerplanar graph.