**A disk-packing algorithm for an origami magic trick**.

M. Bern, E. Demaine, D. Eppstein, and B. Hayes.

*Int. Conf. Fun with Algorithms*, Elba, June 1998.

Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.

*Origami*, A K Peters, 2002, pp. 17–28.^{3}: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001)We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.

(preprint at Erik's web site – BibTeX – CiteSeer)

**Ununfoldable polyhedra**.

M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.

arXiv:cs.CG/9908003.

Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.

*11th Canad. Conf. Comp. Geom.,*1999.

4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.

*Comp. Geom. Theory & Applications*(special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.

Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.

(BibTeX – Erik's publication page – CiteSeer – ACM DL)

**Hinged dissections of polyominos and polyforms**.

E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.

arXiv:cs.CG/9907018.

*11th Canad. Conf. Comp. Geom.,*1999.

*Computational Geometry: Theory and Applications*31 (3): 237–262, 2005 (special issue for 11th CCCG).We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.

(BibTeX – Erik's CCCG publication page – Erik's CGTA publication page – Citations)

**Phutball endgames are hard**.

E. Demaine, M. Demaine, and D. Eppstein.

arXiv:cs.CC/0008025.

*More Games of No Chance*, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.

(BibTeX – Citations – Erik's publications page – CiteSeer)

**Vertex-unfoldings of simplicial manifolds**.

E. Demaine, D. Eppstein, J. Erickson, G. Hart, and J. O'Rourke.

Tech. Reps. 071 and 072, Smith College, 2001.

arXiv:cs.CG/0107023 and cs.CG/0110054.

*18th ACM Symp. Comp. Geom.,*Barcelona, 2002, pp. 237–243.

*Discrete Geometry: In honor of W. Kuperberg's 60th birthday*, Pure and Appl. Math. 253, Marcel Dekker, pp. 215–228, 2003.We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex

**Flat foldings of plane graphs with prescribed angles and edge lengths**.

Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.

arXiv:1408.6771.

*22nd Int. Symp. Graph Drawing*, Würzburg, Germany, 2014.

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 272–283.

*J. Computational Geometry*9 (1): 71–91, 2018.Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

**Folding a paper strip to minimize thickness**.

E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.

arXiv:1411.6371.

*9th International Workshop on Algorithms and Computation (WALCOM 2015)*, Dhaka, Bangladesh.

Springer,*Lecture Notes in Comp. Sci.*8973 (2015), pp. 113–124.

*Journal of Discrete Algorithms*36: 18–26, 2016.

If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.

**Folding polyominoes into (poly)cubes**.

O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.

*27th Canadian Conference on Computational Geometry*, Kingston, Ontario, Canada, 2015, pp. 101–106.

arXiv:1712.09317.

*Int. J. Comp. Geom. & Appl.*, to appear.We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

**Rigid origami vertices: Conditions and forcing sets**.

Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.

arXiv:1507.01644.

*J. Computational Geometry*7 (1): 171–184, 2016.We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.

**Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect**.

J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.

arXiv:1805.04055

*Proc. 24th International Computing and Combinatorics Conference (COCOON 2018)*, Qingdao, China, to appear.

For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.