  We study the reverse shortest path problem on disk graphs in the plane. In
this problem we consider the proximity graph of a set of $n$ disks in the plane
of arbitrary radii: In this graph two disks are connected if the distance
between them is at most some threshold parameter $r$. The case of intersection
graphs is a special case with $r=0$. We give an algorithm that, given a target
length $k$, computes the smallest value of $r$ for which there is a path of
length at most $k$ between some given pair of disks in the proximity graph. Our
algorithm runs in $O^*(n^{5/4})$ randomized expected time, which improves to
$O^*(n^{6/5})$ for unit disk graphs, where all the disks have the same radius.
Our technique is robust and can be applied to many variants of the problem. One
significant variant is the case of weighted proximity graphs, where edges are
assigned real weights equal to the distance between the disks or between their
centers, and $k$ is replaced by a target weight $w$; that is, we seek a path
whose length is at most $w$. In other variants, we want to optimize a parameter
different from $r$, such as a scale factor of the radii of the disks.
  The main technique for the decision version of the problem (determining
whether the graph with a given $r$ has the desired property) is based on
efficient implementations of BFS (for the unweighted case) and of Dijkstra's
algorithm (for the weighted case), using efficient data structures for
maintaining the bichromatic closest pair for certain bicliques and several
distance functions. The optimization problem is then solved by combining the
resulting decision procedure with enhanced variants of the interval shrinking
and bifurcation technique of [4].
