<p>The mentioned block graphs in the question are distance-hereditary. A linear time algorithm for computing the diameter for distance-hereditary graphs is given in [1] (see Theorem 5). </p>

<hr>

<p>[1] <a href="http://www.cs.kent.edu/~dragan/dhgdomclique.pdf" rel="nofollow">Dragan, Feodor F. Dominating cliques in distance-hereditary graphs. Springer Berlin Heidelberg, 1994.</a></p>

CC BY-SA 3.0
2013-07-02T11:25:23.343Z
2013-07-02T11:25:23.343Z
Juho
<p>The eccentricity of a vertex <span class="math-container">$v$</span> is the length of a longest shortest path starting from <span class="math-container">$v$</span>.  The diameter is the maximal eccentricity over all vertices.
Any BFS from a vertex will establish its eccentricity.
A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal eccentricity.</p>

<p>Running a <em><a href="http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search" rel="nofollow noreferrer">lexicographic breadth-first search</a></em>, the end-vertex often has high eccentricity.  In particular, it is guaranteed to have eccentricity at most one less than the diameter for chordal graphs.  For some subclasses of chordal graphs such as <a href="http://www.graphclasses.org/classes/gc_234.html" rel="nofollow noreferrer">interval graphs</a>, it is guaranteed to have maximal eccentricity.  This also holds for some non-chordal classes such as <a href="http://www.graphclasses.org/classes/gc_60.html" rel="nofollow noreferrer"><span class="math-container">$\{\text{AT},\text{claw}\}$</span>-free</a> graphs.</p>

<p>LBFS and BFS are both linear in the size of the graph, but of course if <span class="math-container">$m = \Omega(n^2)$</span> (such as <span class="math-container">$K_n$</span>) then the runtime will not be <span class="math-container">$o(n^2)$</span>.  Your discussion implies that you probably really want a linear algorithm <span class="math-container">$O(m+n)$</span> rather than <span class="math-container">$o(n^2)$</span>.</p>

<p>So for some subclasses of chordal graphs, a linear algorithm is to run LBFS, take the end-vertex, then run BFS starting at that vertex.  For chordal graphs this will determine the diameter with an error of at most 1.  The graphs for which this is exact seem to be those where the even powers are chordal.  These are precisely those chordal graphs that contain no rising sun or <span class="math-container">$(\text{rising sun}- K_2)$</span> subgraph that preserves distances.</p>

<p><a href="https://i.sstatic.net/l7mjT.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/l7mjT.gif" alt="rising sun graph"></a><br>
<sub>(source: <a href="http://www.graphclasses.org/images/g_risingsun.gif" rel="nofollow noreferrer">graphclasses.org</a>)</sub>  </p>

<ul>
<li>Feodor F. Dragan, Falk Nicolai and Andreas Brandstädt, <em>LexBFS-orderings and powers of graphs</em>, WG 1996, LNCS 1197, 166–180.  doi:<a href="http://dx.doi.org/10.1007/3-540-62559-3_15" rel="nofollow noreferrer">10.1007/3-540-62559-3_15</a></li>
</ul>

<p>I do not know if this can be extended to compute the diameter for all chordal graphs precisely.  Corneil's survey seems to indicate that this was still open in 2004.  I also don't know if an analysis has been done on extending the search from one vertex to a small constant number or <span class="math-container">$\log n$</span> starting vertices; this might be interesting to explore.</p>

<ul>
<li>Derek G. Corneil, <em>Lexicographic Breadth First Search – A Survey</em>, WG 2004, LNCS 3353, 1–19. doi:<a href="http://dx.doi.org/10.1007/978-3-540-30559-0_1" rel="nofollow noreferrer">10.1007/978-3-540-30559-0_1</a></li>
</ul>

CC BY-SA 3.0
2013-07-01T17:17:53.747Z
Interesting, thanks! And yes, I did mean $O(n+m)$ rather than $o(n^2)$. Seems like the graphs I care about at the moment don't contain either of the subgraphs mentioned, so this is indeed nice.
Juho
CC BY-SA 4.0
2013-07-01T11:18:49.627Z
2019-02-25T04:48:03.643Z
2019-02-25T04:48:03.643Z
András Salamon
<p>Recall the <em>diameter</em> of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) and returns the length of the longest path found.</p>

<p>It is known that the APSP problem can be solved in optimal $O(n^2)$ time for several graph classes. For general graphs, there is an algebraic graph theoretic approach running in $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. However, computing the diameter is apparently not critically linked to APSP, <a href="http://arxiv.org/abs/1011.6181">as shown by Yuster</a>.</p>

<blockquote>
  <p>Are some non-trivial graph classes known for which the diameter can be computed even faster, say in linear time? </p>
</blockquote>

<p>I am especially interested in chordal graphs, and any subclasses of chordal graphs such as block graphs. For example, I think the diameter of a chordal graph $G$ can be computed in $O(n+m)$ time, if $G$ is uniquely representable as a clique tree. Such a graph is also known as <em>ur-chordal</em>.</p>

CC BY-SA 3.0
2013-06-30T13:08:31.160Z
For the computation of diameter, once the clique tree is given, chordal graphs behave (almost) the same as trees.  Likewise, in an interval graph, a dominating pair (which exists in any AT-free graphs) necessarily decides the diameter.
Yixin Cao
CC BY-SA 3.0
2013-06-30T13:23:38.320Z
@YixinCao But in general, the number of distinct clique trees a chordal graph can have is exponential in the number of vertices. Futhermore, I don't think the diameter is the same in every clique tree. I think this is a problem, but in a ur-chordal graph the diameter of the clique tree is unambigious. Did you have something else in mind?
Juho
CC BY-SA 3.0
2013-06-30T18:17:43.677Z
I'm not saying the diameter of the chordal graph is the same as that of its clique tree.  (A star of $k+1$ vertices can have a clique tree that is a path of $k$ nodes.)  What I meant is the diameter of the graph must be between some pair of leaves (any simplicial vertex in it) in the clique tree.
Yixin Cao
CC BY-SA 3.0
2013-06-30T18:58:28.080Z
@YixinCao OK, now I understand better. Even so, a (fast) algorithm is still not obvious to me. If you have any additional details or references, please feel free!
Juho
<graph-theory><graph-algorithms><shortest-path>
Graph classes for which the diameter can be computed in linear time
Juho
# Graph classes for which the diameter can be computed in linear time

(Asked by: username_0 on 2013-06-30)

Recall the *diameter* of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) and returns the length of the longest path found.

It is known that the APSP problem can be solved in optimal $O(n^2)$ time for several graph classes. For general graphs, there is an algebraic graph theoretic approach running in $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. However, computing the diameter is apparently not critically linked to APSP, [as shown by Yuster](http://arxiv.org/abs/1011.6181).

> Are some non-trivial graph classes known for which the diameter can be computed even faster, say in linear time?

I am especially interested in chordal graphs, and any subclasses of chordal graphs such as block graphs. For example, I think the diameter of a chordal graph $G$ can be computed in $O(n+m)$ time, if $G$ is uniquely representable as a clique tree. Such a graph is also known as *ur-chordal*.

**Tags:** graph-theory, graph-algorithms, shortest-path
> **Comments:**
> **username_1**: For the computation of diameter, once the clique tree is given, chordal graphs behave (almost) the same as trees.  Likewise, in an interval graph, a dominating pair (which exists in any AT-free graphs) necessarily decides the diameter.  
> **username_0**: @YixinCao But in general, the number of distinct clique trees a chordal graph can have is exponential in the number of vertices. Futhermore, I don't think the diameter is the same in every clique tree. I think this is a problem, but in a ur-chordal graph the diameter of the clique tree is unambigious. Did you have something else in mind?  
> **username_1**: I'm not saying the diameter of the chordal graph is the same as that of its clique tree.  (A star of $k+1$ vertices can have a clique tree that is a path of $k$ nodes.)  What I meant is the diameter of the graph must be between some pair of leaves (any simplicial vertex in it) in the clique tree.  
> **username_0**: @YixinCao OK, now I understand better. Even so, a (fast) algorithm is still not obvious to me. If you have any additional details or references, please feel free!  

---

## 2 answers

### Answer by username_2 on 2013-07-01. Score: 9 | Accepted answer

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$. The diameter is the maximal eccentricity over all vertices.
Any BFS from a vertex will establish its eccentricity.
A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal eccentricity.

Running a *[lexicographic breadth-first search](http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search)*, the end-vertex often has high eccentricity. In particular, it is guaranteed to have eccentricity at most one less than the diameter for chordal graphs. For some subclasses of chordal graphs such as [interval graphs](http://www.graphclasses.org/classes/gc_234.html), it is guaranteed to have maximal eccentricity. This also holds for some non-chordal classes such as [$\{\text{AT},\text{claw}\}$-free](http://www.graphclasses.org/classes/gc_60.html) graphs.

LBFS and BFS are both linear in the size of the graph, but of course if $m = \Omega(n^2)$ (such as $K\_n$) then the runtime will not be $o(n^2)$. Your discussion implies that you probably really want a linear algorithm $O(m+n)$ rather than $o(n^2)$.

So for some subclasses of chordal graphs, a linear algorithm is to run LBFS, take the end-vertex, then run BFS starting at that vertex. For chordal graphs this will determine the diameter with an error of at most 1. The graphs for which this is exact seem to be those where the even powers are chordal. These are precisely those chordal graphs that contain no rising sun or $(\text{rising sun}- K\_2)$ subgraph that preserves distances.

[![rising sun graph](https://i.sstatic.net/l7mjT.gif)](https://i.sstatic.net/l7mjT.gif)  
(source: [graphclasses.org](http://www.graphclasses.org/images/g_risingsun.gif))

* Feodor F. Dragan, Falk Nicolai and Andreas Brandstädt, *LexBFS-orderings and powers of graphs*, WG 1996, LNCS 1197, 166–180. doi:[10.1007/3-540-62559-3\_15](http://dx.doi.org/10.1007/3-540-62559-3_15)

I do not know if this can be extended to compute the diameter for all chordal graphs precisely. Corneil's survey seems to indicate that this was still open in 2004. I also don't know if an analysis has been done on extending the search from one vertex to a small constant number or $\log n$ starting vertices; this might be interesting to explore.

* Derek G. Corneil, *Lexicographic Breadth First Search – A Survey*, WG 2004, LNCS 3353, 1–19. doi:[10.1007/978-3-540-30559-0\_1](http://dx.doi.org/10.1007/978-3-540-30559-0_1)

> **Comments:**
> **username_0**: Interesting, thanks! And yes, I did mean $O(n+m)$ rather than $o(n^2)$. Seems like the graphs I care about at the moment don't contain either of the subgraphs mentioned, so this is indeed nice.  

---

### Answer by username_0 on 2013-07-02. Score: 3

The mentioned block graphs in the question are distance-hereditary. A linear time algorithm for computing the diameter for distance-hereditary graphs is given in [1] (see Theorem 5).

---

[1] [Dragan, Feodor F. Dominating cliques in distance-hereditary graphs. Springer Berlin Heidelberg, 1994.](http://www.cs.kent.edu/~dragan/dhgdomclique.pdf)


---

