Maximum packing for biconnected outerplanar graphs

DOI10.1016/S0166-218X(99)00176-6MaRDI QIDQ1962022zbMATH OpenOpenAlexFDO

Authors Tomas Kovacs, Andrzej Lingas

Publication date 15 September 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00176-6

zbMATH Keywords

biconnected outerplanar graphsdirected acyclic graphsmaximum packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Edge-packing in planar graphs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Maximum tree-packing in time \(O(n^{5/2})\)
• scientific article; zbMATH DE number 3963193
• Edge-packing planar graphs by cyclic graphs

Cites work

• Approximation algorithms for maximum two-dimensional pattern matching
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Easy problems for tree-decomposable graphs
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Generalized planar matching
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 4072379 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Introduction to algorithms
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Maximum tree-packing in time \(O(n^{5/2})\)
• On generalized matching problems
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• On the completeness of a generalized matching problem
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Subtree Isomorphism in O(n5/2)
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(3)

• Edge-packing in planar graphs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Outer-connected open packing sets in graphs

This page was built for publication: Maximum packing for biconnected outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962022)