EDGE-PACKING IN PLANAR GRAPHS

Maximum G Edge-Packing (EPack(G)) is the problem of finding the maximu m number of edge-disjoint isomorphic copies of a fixed guest graph G i n a host graph H. This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is s olvable in polynomial time when both G and H are trees. Edge-packing i s solvable in linear time when H is outerplanar and G is either a 3-cy cle or a k-star (a graph isomorphic to K-1,K-k) Edge-packing is NP-com plete when H is planar and G is either a cycle or a tree with greater than or equal to 3 edges. A strategy for developing polynomial-time ap proximation algorithms for planar hosts is exemplified by a linear-tim e approximation algorithm that finds a k-star edge-packing of size at least half the optimal.