Edge-Packing in Planar Graphs

Maximum G Edge-Packing (EPack _G ) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K _1,k ). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with \(\geq 3\) edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k -star edge-packing of size at least half the optimal.

Authors and Affiliations

1. Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061-0106, USA heath@cs.vt.edu, , , , , , US

   L. S. Heath

2. Department of Information Systems and Computer Science, Ateneo De Manila University, Manila 0917, Philippines jpv@admu.edu.ph, , , , , , PH

   J. P. C. Vergara

Received May 1995, and in revised form November 1995, and in final form December 1997.

Reprints and permissions