Vertex-unfoldings of simplicial manifolds

Written with Erik D. Demaine, David Eppstein, George W. Hart, and Joseph O'Rourke.

Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday (András Bezdek, editor), Marcel-Dekker, 2003, pp. 215-228.

Proceedings of the 18th Annual ACM Symposium on Computational Geometry, 237-243, 2002.


We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.

Publications - Jeff Erickson ( 23 Jun 2003