Edge-packing planar graphs by cyclic graphs (Q1382263)

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.