  The graph-navigability problem concerns how one can find as short paths as
possible between a pair of vertices, given an incomplete picture of a graph. We
study the navigability of graphs where the vertices are tagged by a number
(between 1 and the total number of vertices) in a way to aid navigation. This
information is too little to ensure errorfree navigation but enough, as we will
show, for the agents to do significantly better than a random walk. In our
setup, given a graph, we first assign information to the vertices that agents
can utilize for their navigation. To evaluate the navigation, we calculate the
average distance traveled over random pairs of source and target and different
graph realizations. We show that this type of embedding can be made quite
efficiently; the more information is embedded, the more efficient it gets. We
also investigate the embedded navigational information in a standard graph
layout algorithm and find that although this information does not make
algorithms as efficient as the above-mentioned schemes, it is significantly
helpful.
