Approximating the Diameter of Planar Graphs in Near Linear Time

Oren Weimann, Raphael Yuster

We present a $(1+\epsilon )$-approximation algorithm running in $O(f(\epsilon )\cdot n{\log }^{4}n)$ time for finding the diameter of an undirected planar graph with non-negative edge lengths.