  How efficiently can we find an unknown graph using distance or shortest path
queries between its vertices? Let $G = (V,E)$ be an unweighted, connected graph
of bounded degree. The edge set $E$ is initially unknown, and the graph can be
accessed using a \emph{distance oracle}, which receives a pair of vertices
$(u,v)$ and returns the distance between $u$ and $v$. In the
\emph{verification} problem, we are given a hypothetical graph $\hat G =
(V,\hat E)$ and want to check whether $G$ is equal to $\hat G$. We analyze a
natural greedy algorithm and prove that it uses $n^{1+o(1)}$ distance queries.
In the more difficult \emph{reconstruction} problem, $\hat G$ is not given, and
the goal is to find the graph $G$. If the graph can be accessed using a
\emph{shortest path oracle}, which returns not just the distance but an actual
shortest path between $u$ and $v$, we show that extending the idea of greedy
gives a reconstruction algorithm that uses $n^{1+o(1)}$ shortest path queries.
When the graph has bounded treewidth, we further bound the query complexity of
the greedy algorithms for both problems by $\tilde O(n)$. When the graph is
chordal, we provide a randomized algorithm for reconstruction using $\tilde
O(n)$ distance queries.
