I'd like to take the occasion and sketch my view on reconstruction problems in graph theory: I see a graph as a set of subjects with a relation between (some of) them. Each node (= subject) has a limited knowledge of the whole graph. The question is how many of those subjects have to put their knowledge together to know the whole graph. Of course, this depends on the kind of limited knowledge each subject (= node) has. In case it knows everything but its own relations to the rest of the graph, we have Ulam's reconstruction problem. Another natural kind of limited knowledge would be: all relations except those between the most distant nodes. Or: all relations within a neighbourhood of fixed size and nothing else.
I find it enlightening to compare this situation to the case of reconstructing a 3D object from its 2D projections (another kind of limited knowledge).