A significant number of packaging products can be represented as folded structures. This contribution demonstrates an approach for generating a set of feasible flat patterns based upon a graph representation of the folded structures. It presents algorithms to detect several typical design features. In order to present alternative flat patterns with different properties to the designer, it is preferred to first generate all feasible spanning trees. Two options to decrease the number of generated spanning trees are then proposed: user constraints and overlapping features. Each of these reduction possibilities is examined, and several practical examples with outcomes are shown. The presented framework shows a decrease of up to 98.5% in the number of possible flat patterns for the investigated parts.