  How efficiently can we find an unknown graph using distance queries between
its vertices? We assume that the unknown graph is connected, unweighted, and
has bounded degree. The goal is to find every edge in the graph. This problem
admits a reconstruction algorithm based on multi-phase Voronoi-cell
decomposition and using $\tilde O(n^{3/2})$ distance queries.
  In our work, we analyze a simple reconstruction algorithm. We show that, on
random $\Delta$-regular graphs, our algorithm uses $\tilde O(n)$ distance
queries. As by-products, we can reconstruct those graphs using $O(\log^2 n)$
queries to an all-distances oracle or $\tilde O(n)$ queries to a betweenness
oracle, and we bound the metric dimension of those graphs by $\log^2 n$.
  Our reconstruction algorithm has a very simple structure, and is highly
parallelizable. On general graphs of bounded degree, our reconstruction
algorithm has subquadratic query complexity.
