In this paper we study the Forest Wrapping Problem (FWP) which can be stated as follows: given a connected graph G = (V, E), with |V| = n, let ?0 be a partition of G into K (not necessarily connected) components, find a connected partition ?* of G that wraps ?0 and has maximum number of components.The Forest Wrapping problem is NP-complete on grid graphs while is solvable in O(n log n) time on ladder graphs. We provide a two-phase O(n2) time algorithm for solving FWP on outerplanar graphs.
['Isabella Lari', 'Federica Ricca', 'Andrea Scozzari']
The Forest Wrapping Problem on Outerplanar Graphs