Maximum packing for biconnected outerplanar graphs (Q1962022)

A \(G\)-packing of a graph \(H\) is a set of vertex-disjoint subgraphs \(H_{1}, H_{2}, \ldots ,H_{l}\) of \(H\) such that each \(H_{i}\) is isomorphic to \(G\). The problem of maximum \(G\)-packing in \(H\) is to determine the maximum cardinality of a \(G\)-packing of \(H\). In general, the problem is NP-complete, even when \(H\) is a planar graph, and is generally, as hard as the subgraph isomorphism problem. Recently, for trees an \(O(n^{5/2})\) algorithm has been reported. In this paper, the authors present an \(O((n_{g}n_{h})^{2})\) algorithm for the problem, when \(H\) and \(G\) are biconnected outerplanar graphs, and \(n_{g}= |V(G)|\) and \(n_{h} =\;|V(H)|\). The method involves meticulous calculations of embeddings of partially triangulated polygons of \(G\) into such polygons of \(H\). Extensions of the problem to topological \(G\)-packing and homeomorphic \(G\)-packing are also discussed. The result has potential applications to image processing, chemical structure analysis, and computational biology.