On Sat, 24 Jun 2017, David Wilson wrote:
1. For a given polyhedron, what is the minimal number edges that need to be cut to unfold it into a connected planar surface? For example, 3 edges are necessary for a tetrahedron, I think 7 for a cube.
Allan Wechsler's conjecture that the cuts form a spanning tree is correct for convex polyhedra with no flat edges. (This follows from Lemmas 3 and 4 of http://erikdemaine.org/papers/Ununfoldable/ , the mentioned Bern et al. paper.) So the count is always number of vertices minus 1 for this case. Even for polyhedra homeomorphic to a sphere, the number of cuts can be smaller than the number of vertices minus one, at least in special cases where a closed loop unfolds flat. See Figure 2 of http://erikdemaine.org/papers/Ununfoldable/ I'm pretty sure that this example has other edge unfoldings that use V-1 cuts, so this shows some variation even without tori. I'm pretty sure you'd always need Omega(V) cuts. In general the number of cuts should be at most V-1 + genus, and I expect that "usually" (for small perturbations of a surface) all edge unfoldings have exactly V-1 + genus cuts.
5. Is there a convex polyhedron for which some unfolding exhibits overlapping faces in the plane? If so, what is the smallest number of faces on such a polyhedron?
There's a lot of discussion about the "edge unfolding of convex polyhedra" problem in our book Geometric Folding Algorithms [http://gfalop.org/] (Chapter 22). Also e.g. mentions the results above and shows the Mathworld examples, among others. Another known experimental result is that, as n goes to infinity, most unfoldings (approaching 100%) of a random n-vertex convex polyhedron (say, convex hull of random points on a sphere) are *overlapping*. So there are lots of examples. :-) Beyond the old Bern et al. paper, finding a nonoverlapping edge unfolding of a nonconvex polyhedron is in fact NP-complete: http://erikdemaine.org/papers/UnfoldingComplexity_CCCG2011/ Erik -- Erik Demaine | edemaine@mit.edu | http://erikdemaine.org/