graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the diameter of a connected undirected graph is the farthest

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects, points, people, or ideas are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two co ...

between any two of its vertices. That is, it is the

diameter of a set In mathematics, the diameter of a set of points in a metric space is the largest distance between points in the set. As an important special case, the diameter of a metric space is the largest distance between any two points in the space. This ...

for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs. The diameter of a disconnected graph may be defined to be infinite, or undefined.

Graphs of low diameter

The

degree diameter problem In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is boun ...

seeks tight relations between the diameter, number of vertices, and degree of a graph. One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter. For any fixed degree, this maximum size is exponential in diameter, with the base of the exponent depending on the degree. The

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

of a graph, the length of its shortest cycle, can be at most

2k+1

for a graph of diameter

k

. The

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

s for which the girth is exactly

2k+1

are the

Moore graph In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must ...

s. Only finitely many Moore graphs exist, but their exact number is unknown. They provide the solutions to the degree diameter problem for their degree and diameter.

Small-world network A small-world network is a graph characterized by a high clustering coefficient and low distances. In an example of the social network, high clustering implies the high probability that two friends of one person are friends themselves. The l ...

s are a class of graphs with low diameter, modeling the real-world phenomenon of

six degrees of separation Six degrees of separation is the idea that all people are six or fewer social connections away from each other. As a result, a chain of "friend of a friend" statements can be made to connect any two people in a maximum of six steps. It is al ...

social network A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of Dyad (sociology), dyadic ties, and other Social relation, social interactions between actors. The social network per ...

Algorithms

In arbitrary graphs

The diameter of a graph can be computed by using a

shortest path algorithm In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes. For instance, in a graph with positive edge weights, this can be done by repeatedly using

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...

, once for each possible starting vertex. In a graph with

n

vertices and

m

edges, this takes time

O(mn+n^2\log n)

. Computing all-pairs shortest paths is the fastest known method for computing the diameter of a weighted graph exactly. In an unweighted-graph, Dijkstra's algorithm may be replaced by a

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...

, giving time

O(mn)

. Alternatively, the diameter may be computed using an algorithm based on

fast matrix multiplication In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and nu ...

, in time proportional to the time for multiplying

n\times n

matrices, approximately

O(n^)

using known matrix multiplication algorithms. For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication. Assuming the

strong exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, 2^. Mor ...

, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time

O(n^)

for any

\varepsilon>0

. It is possible to approximate the diameter of a weighted graph to within an

approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

of 3/2, in time

\tilde O(\min(m^,mn^)

, where the

\tilde O

notation hides logarithmic factors in the time bound. Under the exponential time hypothesis, no substantially more accurate approximation, substantially faster than all pairs shortest paths, is possible.

In special classes of graphs

The diameter can be computed in linear time for

interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. In ...

s, and in near-linear time for graphs of bounded

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests ...

. In

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertex (graph theory), vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest pat ...

s, the diameter can be found in the subquadratic time bound

\tilde O(n^)

. In any class of graphs closed under

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

s, such as the

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s, it is possible to compute the diameter in subquadratic time, with an exponent depending on the graph family.

References

{{reflist, refs= {{citation , last1 = Amaral , first1 = L. A. N. , last2 = Scala , first2 = A. , last3 = Barthélémy , first3 = M. , last4 = Stanley , first4 = H. E. , date = September 2000 , doi = 10.1073/pnas.200327197 , issue = 21 , journal = Proceedings of the National Academy of Sciences , pages = 11149–11152 , title = Classes of small-world networks , volume = 97, doi-access = free , pmid = 11005838 , arxiv = cond-mat/0001458 {{citation , last1 = Bergé , first1 = Pierre , last2 = Ducoffe , first2 = Guillaume , last3 = Habib , first3 = Michel , doi = 10.1007/s00224-023-10153-9 , issue = 1 , journal = Theory of Computing Systems , mr = 4699679 , pages = 144–193 , title = Subquadratic-time algorithm for the diameter and all eccentricities on median graphs , volume = 68 , year = 2024, arxiv = 2110.02709 {{citation , last1 = Bringmann , first1 = Karl , last2 = Husfeldt , first2 = Thore , last3 = Magnusson , first3 = Måns , doi = 10.1007/s00453-020-00680-z , issue = 8 , journal = Algorithmica , mr = 4132892 , pages = 2292–2315 , title = Multivariate analysis of orthogonal range searching and graph distances , volume = 82 , year = 2020, doi-access = free {{citation , last1 = Chechik , first1 = Shiri , last2 = Larkin , first2 = Daniel H. , last3 = Roditty , first3 = Liam , last4 = Schoenebeck , first4 = Grant , last5 = Tarjan , first5 = Robert Endre , last6 = Vassilevska Williams , first6 = Virginia , editor-last = Chekuri , editor-first = Chandra , contribution = Better approximation algorithms for the graph diameter , doi = 10.1137/1.9781611973402.78 , pages = 1041–1052 , publisher = SIAM , title = Proceedings of the Twenty-Fifth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 , year = 2014, isbn = 978-1-61197-338-9 {{citation , last1 = Cygan , first1 = Marek , last2 = Gabow , first2 = Harold N. , last3 = Sankowski , first3 = Piotr , contribution = Algorithmic applications of Baur-Strassen's theorem: shortest cycles, diameter and matchings , doi = 10.1109/FOCS.2012.72 , pages = 531–540 , publisher = IEEE Computer Society , title = 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 , year = 2012, arxiv = 1204.1616 , isbn = 978-0-7695-4874-6 {{citation , last = Dalfó , first = C. , doi = 10.1016/j.laa.2018.12.035 , journal = Linear Algebra and Its Applications , mr = 3901732 , pages = 1–14 , title = A survey on the missing Moore graph , volume = 569 , year = 2019, hdl = 2117/127212 , s2cid = 126689579 , hdl-access = free , url = https://upcommons.upc.edu/bitstream/2117/127212/1/monster%2818oct2017-rev30dec2018%29.pdf {{citation , last1 = Ducoffe , first1 = Guillaume , last2 = Habib , first2 = Michel , last3 = Viennot , first3 = Laurent , arxiv = 1907.04385 , doi = 10.1137/20M136551X , issue = 5 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

, mr = 4502132 , pages = 1506–1534 , title = Diameter, eccentricities and distance oracle computations on {{mvar, H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension , volume = 51 , year = 2022 {{citation , last1 = Miller , first1 = Mirka , author1-link = Mirka Miller , last2 = Širáň , first2 = Jozef , title = Moore graphs and beyond: A survey of the degree/diameter problem , journal =

Electronic Journal of Combinatorics The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Geor ...

, volume = Dynamic survey , pages = DS14 , year = 2005 , url = http://www.combinatorics.org/ojs/index.php/eljc/article/download/DS14/pdf {{citation , last = Olariu , first = Stephan , doi = 10.1080/00207169008803870 , issue = 3–4 , journal = Int. J. Comput. Math. , pages = 121–128 , title = A simple linear-time algorithm for computing the center of an interval graph , volume = 34 , year = 1990 {{citation , last1 = Roditty , first1 = Liam , last2 = Vassilevska Williams , first2 = Virginia , author2-link = Virginia Vassilevska Williams , editor1-last = Boneh , editor1-first = Dan , editor2-last = Roughgarden , editor2-first = Tim , editor3-last = Feigenbaum , editor3-first = Joan , contribution = Fast approximation algorithms for the diameter and radius of sparse graphs , doi = 10.1145/2488608.2488673 , pages = 515–524 , publisher = Association for Computing Machinery , title = Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , year = 2013, isbn = 978-1-4503-2029-0 Graph distance Graph invariants Computational problems in graph theory

Graphs of low diameter

Algorithms

In arbitrary graphs

In special classes of graphs

See also

References