dense graph


Definition: A graph in which the number of edges is close to the possible number of edges.

Generalization (I am a kind of ...)

Specialization (... is a kind of me.)
complete graph.

See also sparse graph, adjacency-matrix representation.

Note: A directed graph can have at most n(n-1) edges, where n is the number of vertices. An undirected graph can have at most n(n-1)/2 edges.

There is no strict distinction between sparse and dense graphs. Typically, a sparse (connected) graph has about as many edges as vertices, and a dense graph has nearly the maximum number of edges.

Author: PEB

More information

Dense_graph [Wikipedia]

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 December 2019.
HTML page formatted Mon Dec 2 09:10:23 2019.

Cite this as:
Paul E. Black, "dense graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 December 2019. (accessed TODAY) Available from: