# Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs

Consider an unweighted undirected bi-connected planar graph.

Let $l_{v,u}$ be the length of the shortest path between nodes $v$ and $u$.

Let $l_{max}$ be the length of the longest shortest path from any node to any other node.

The question is:

Are there any known non-trivial upper/lower bounds for $l_{max}$?

It would also help if the bounds are for more general types of graphs.

Another interesting way of looking at the problem is:

• $l_{max}$ is the maximal number of hops it takes to send a packet in a network from any terminal to any other, when using the shortest possible path.

Please post any link/reference that might be relevant, even if it does not directly solve the problem. Thanks in advance!

• Since the graph is biconnected, any two nodes lie on a cycle, and so $\ell_\max \le n/2$. The $n$-cycle is planar and achieves this bound. May 12, 2011 at 22:30

$l_{max}$ is called diameter of a graph. I hope this paper will be helpful