Maximum packing for biconnected outerplanar graphs
type: Item
instance of: scholarly article
title: Maximum packing for biconnected outerplanar graphs
zbMATH Open document ID: 0944.05075
DOI: 10.1016/S0166-218X(99)00176-6
author: Tomas Kovacs
author: Andrzej Lingas
published in: Discrete Applied Mathematics
publication date: 2000-09-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1394992
zbMATH Keywords: maximum packing
zbMATH Keywords: biconnected outerplanar graphs
zbMATH Keywords: directed acyclic graphs
MaRDI profile type: Publication
cites work: Approximation algorithms for maximum two-dimensional pattern matching
cites work: Easy problems for tree-decomposable graphs
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Generalized planar matching
cites work: Q3795218
cites work: Introduction to algorithms
cites work: Faster algorithms for subgraph isomorphism of κ-connected partial κ-trees
cites work: Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
cites work: On generalized matching problems
cites work: On the completeness of a generalized matching problem
cites work: Subgraph isomorphism for biconnected outerplanar graphs in cubic time
cites work: Maximum tree-packing in time \(O(n^{5/2})\)
cites work: On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
cites work: Q3804190
cites work: On the complexity of finding iso- and other morphisms for partial \(k\)- trees
cites work: Subtree Isomorphism in O(n5/2)
cites work: Linear algorithms to recognize outerplanar and maximal outerplanar graphs
cites work: Q3992847
cites work: The subgraph isomorphism problem for outerplanar graphs
full work available at URL: s0166-218x(99)00176-6
OpenAlex ID: W2105366839
description: scientific article; zbMATH DE number 1394992