**Reference**:- Erik D. Demaine, Martin L. Demaine, and Vi Hart, “Computational Balloon Twisting: The Theory of Balloon Polyhedra”, in
*Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008)*, Montréal, Québec, Canada, August 13–15, 2008. **Abstract**:- This paper builds a general mathematical and algorithmic theory for balloon-twisting structures, from balloon animals to balloon polyhedra, by modeling their underlying graphs (edge skeleta). In particular, we give algorithms to find the fewest balloons that can make exactly a desired graph or, using fewer balloons but allowing repeated traversal or shortcuts, the minimum total length needed by a given number of balloons. In contrast, we show NP-completeness of determining whether such an optimal construction is possible with balloons of equal length.
**Comments**:- A short version of the paper appeared on pages 139--142.
**Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PDF (2751k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Balloons_ShapingSpace2 (Balloon Polyhedra)

See also other papers by Erik Demaine.

Last updated January 4, 2022 by Erik Demaine.