Geometry of unweighted k-nearest neighbor graphs

Consider an unweighted k-nearest neighbor graph that has been built on a random sample from some unknown density p on R^d. Assume we are given nothing but the unweighted (!) adjacency matrix of the graph: we know who is among the k nearest neighbors of whom, but we do not know the point locations or any distances or similarity values between the points. Is it then possible to recover the original point configuration or estimate the underlying density p, just from the adjacency matrix of the unweighted graph? As I will show in the talk, the answer is yes. I present a proof for this result, and also discuss relations to the problem of ordinal embedding.