Edge-packing planar graphs by cyclic graphs
type: Item
instance of: scholarly article
title: Edge-packing planar graphs by cyclic graphs
zbMATH Open document ID: 0899.05043
DOI: 10.1016/S0166-218X(97)00083-8
author: Lenwood S. Heath
author: John Paul C. Vergara
published in: Discrete Applied Mathematics
publication date: 1998-03-25T00:00:00Z
full work available at URL: dam
review text: Let \(G\) and \(H\) be graphs. An edge-packing of \(G\) into \(H\) is a collection of edge-disjoint subgraphs of \(H\) each isomorphic to \(G\). A maximum edge-packing is an edge-packing with the largest number of subgraphs. In this paper, the case when \(G\) has at least one cycle and \(H\) is planar is considered. Under a wide range of conditions on \(G\), determining whether a packing with at least \(k\) subgraphs is shown to be NP-complete. In the process, some difficulties with the proof in \textit{D. G. Corneil}, \textit{S. Masuyama} and \textit{S. L. Hakimi} [Edge-disjoint packages of graphs, Discrete Appl. Math. 50, No. 2, 135-148 (1994; Zbl 0793.68114)] are identified.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1133159
zbMATH Keywords: planar graph
zbMATH Keywords: edge-packing
zbMATH Keywords: NP-complete
reviewed by: Charles J. Colbourn
MaRDI profile type: Publication
cites work: Q4773298
cites work: Edge-disjoint packings of graphs
cites work: Edge-packing in planar graphs
cites work: Dividing a Graph into Triconnected Components
cites work: Planar Formulae and Their Uses
cites work: A structural characterization of planar combinatorial graphs
description: scientific article; zbMATH DE number 1133159