It is known that graphs of doubling dimension O(log log n) can be augmented to become navigable. We show that for doubling dimension 》 log log n, an infinite family of graphs cannot be augmented to become navigable. Our proof uses a counting argument which enable us to consider any kind of augmentations. In particular we do not restrict our analysis to the case of symmetric distributions, nor to distributions for which the choice of the long range link at a node must be independent from the choices of long range links at other nodes.
展开▼
