  We consider the problem of computing the diameter of a unicycle graph (i.e.,
a graph with a unique cycle). We present an O(n) time algorithm for the
problem, where n is the number of vertices of the graph. This improves the
previous best O(n \log n) time solution [Oh and Ahn, ISAAC 2016]. Using this
algorithm as a subroutine, we solve the problem of adding a shortcut to a tree
so that the diameter of the new graph (which is a unicycle graph) is minimized;
our algorithm takes O(n^2 \log n) time and O(n) space. The previous best
algorithms solve the problem in O(n^2 \log^3 n) time and O(n) space [Oh and
Ahn, ISAAC 2016], or in O(n^2) time and O(n^2) space [Bil\`o, ISAAC 2018].

Data Structures and Algorithms;Computational Geometry