NIST

sparse graph

(definition)

Definition: A graph in which the number of edges is much less than the possible number of edges.

Generalization (I am a kind of ...)
graph.

See also dense graph, complete graph, adjacency-list 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. Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if |E| = O(|V|k) and 1 < k < 2. |E| is the number of edges, and |V| is the number of vertices.
Preiss reference from Andreas Leiser <andreas.leiser@bluewin.ch> 22 December 2003

Author: PEB


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

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

Entry modified 14 August 2008.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "sparse graph", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/sparsegraph.html

to NIST home page