I. Introduction
One of the most basic graph parameters, the diameter is the largest of the shortest paths distances between pairs of vertices in the graph. Estimating the graph diameter is important in many applications (see e.g. [CGLM12], [TK11], [MLH09]). For instance, the diameter measures how fast information spreads in networks, which is central for paradigms such as distributed and sublinear algorithms.