Sparse vs. Dense Graphs

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Sparse vs. Dense Graphs

Informally, a graph with relatively few edges is sparse, and a graph with many edges is dense. The following definition defines precisely what we mean when we say that a graph ``has relatively few edges'':

Definition (Sparse Graph) A sparse graph is a graph in which .

For example, consider a graph with n nodes. Suppose that the out-degree of each vertex in G is some fixed constant k. Graph G is a sparse graph because .

A graph that is not sparse is said to be dense:

Definition (Dense Graph) A dense graph is a graph in which .

For example, consider a graph with n nodes. Suppose that the out-degree of each vertex in G is some fraction f of n, . E.g., if n=16 and f=0.25, the out-degree of each node is 4. Graph G is a dense graph because .