"The algorithm computes a spanning tree of the dual graph of the polyhedron P. To this spanning tree we associate an isometric mapping of the faces of P to the plane such that all faces that are adjacent in the spanning tree are adjacent in the image of P too. The goal is to find a spanning tree such that the image of P under the associated mapping has no overlappings.To compute the unfolding we use a method derived from Prim's algorithm to compute a minimal spanning tree from a graph with respect to weigthing of each edge (cf. Corman et al. Introduction to Algorithms). Prim's algorithm starts to build the tree with one element and than repeats to add elements that are adjacent to those already in the tree. Here the element with the lowest weight is choosen. Our modification of the algorithm is that we only add the element to the tree if it does not "overlap" with those elements that are already in the tree. Here "overlap" means that we look at the associated map as described above. The weighting we use is the length of the edge between to elements.

One remark here is that if no element can be added to the tree without overlapping, we build a new tree. Consequently the unfolding is not always connected.

This methods performs fast and well for a lot of examples. Anyway there is a second method called "improveUnfolding" designed to reduce the number of components of the "unfolding" if it is not connected. The reducing is done by cutting parts of on component and adding them to another component, trying to make a component vanish."

Pages created by: Kristin Baldassaro, Sasha Berkoff, Asten Buckles, Jinghua Fan, Joseph O'Rourke, Aye Thuzar; June 2003.