Enumerating All Convex Polyhedra Glued from Squares in Polynomial Time

Abstract

We present an algorithm that enumerates and classifies all edge-to-edge gluings of unit squares that correspond to convex polyhedra. We show that the number of such gluings of $n$ squares is polynomial in $n$, and the algorithm runs in time polynomial in $n$ (pseudopolynomial if $n$ is considered the only input). Our technique can be applied in several similar settings, including gluings of regular hexagons and triangles.

8 pages, 6 figures

References in corpus (1)

• The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings