A circle packing on the 2-sphere is a collection of interior disjoint circles whose contact graph is a triangulated simplicial 2-complex homeomorphic to the sphere. The celebrated Koebe-Andre’ev-Thurston theorem shows that such packings are globally rigid in the sense that up to Möbius transformations of the sphere to itself the packing is uniquely determined by its contact graph. Similar results hold when circles are allowed to overlap their neighbors. A c-polyhedron is a natural generalization of circle packings to collections of circles where neighboring circles may overlap, be tangent, or even be disjoint, and where the generalized constraint graph (no longer a contact graph) is a CW complex homeomorphic to the skeleton of a polyhedron. Surprisingly, in this more general setting, it has been shown that global rigidity type theorems do not hold for all possible c-polyhedra. In this talk we give an overview of the problem and its history and discuss two of our recent results in which we recover some rigidity for sub-classes of c-polyhedra. Namely, with an appropriate notion of convex, we show that convex non-unitary c-polyhedra with hyperbolic faces are globally rigid and that almost all triangulated c-polyhedra are locally rigid.