Approximating the Diameter of Planar Graphs in Near Linear Time
arXiv:1112.1116
Abstract
We present a $(1+ε)$-approximation algorithm running in $O(f(ε)\cdot n \log^4 n)$ time for finding the diameter of an undirected planar graph with non-negative edge lengths.