<p>$l_{max}$ is called <a href="http://mathworld.wolfram.com/GraphDiameter.html">diameter of a graph</a>.
I hope <a href="http://dcg.epfl.ch/files/content/shared/files/diam.pdf">this</a> paper will be helpful</p>

CC BY-SA 3.0
2011-05-13T01:24:32.953Z
2011-05-13T01:24:32.953Z
D-503
<p>Consider an unweighted undirected bi-connected planar graph.</p>

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

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

<p>The question is:</p>

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

<p>It would also help if the bounds are for more general types of graphs.</p>

<p>Another interesting way of looking at the problem is:</p>

<ul>
<li>$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.</li>
</ul>

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

CC BY-SA 3.0
2011-05-12T22:30:35.617Z
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.
Suresh Venkat
<graph-theory><co.combinatorics>
Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs
George
# Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs

(Asked by: username_0 on 2011-05-12)

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!

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-05-13. Score: 6 | Accepted answer

$l\_{max}$ is called [diameter of a graph](http://mathworld.wolfram.com/GraphDiameter.html).
I hope [this](http://dcg.epfl.ch/files/content/shared/files/diam.pdf) paper will be helpful


---

