Edge-packing planar graphs by cyclic graphs Original Research Article

MaximumG edge-packing is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graphG in a host graphH. This paper considers the cases whereG andH are planar andG is cyclic. Recent work on the general problem is surveyed, inadequacies and limitations in these results are identified, and NP-completeness proofs for key cases are presented.