A Graph's Density and Sparsity

1. A graph is dense when |E| (edges) is closest to $|V|^2$.
2. A graph is sparse when |E| is closer to $|V|$.

What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time conceptualizing why the above two rules are true.

Also can someone elaborate on why if a graph is sparse, it should be represented with an adj list and why if it is dense, it is best to use an adjacency matrix instead?

• Where did you get those two rules from? Can you provide a citation? The second rule isn't even grammatical, and doesn't make any sense -- a word seems to be missing. Are you sure you copied it down right? – D.W. Mar 17 '16 at 6:58
• @D.W. I fixed the wording. I could have sworn it was not like that the first time around... Sorry about that! – Jonathan Mar 17 '16 at 7:34
• A source is still missing. It would be interesting because these to "rules" are not well-defined. What do "closer" and "closest" mean? Where's the threshold? – Raphael Mar 17 '16 at 8:27
• You are asking three very different questions, all in one post. Don't do that. Plus, the two questions that can be answered have answers in every introductory textbook. – Raphael Mar 17 '16 at 8:28
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Mar 17 '16 at 8:28

The notation $|V|$ here means the number of vertices in your graph. Likewise, $|E|$ is used to denote the number of edges. We typically say that a graph is sparse whenever $|E| \in O(|V|)$ - i.e there are few enough edges. Similarly, we say that a graph is dense whenever $|E| \in \Theta(|V|^2)$ - i.e there are many edges in your graph. These are not really rules, but rather just the terminology one often uses in textbooks.

An adjacency matrix requires $\Theta(|V|^2)$ space to store, while an adjacency list requires $\Theta(|V| + |E|)$ space to store. So when the graph is sparse, using an adjacency matrix is wasteful in terms of space usage, even though answering queries may be faster. On the other hand, is the graph is dense, then both representations require a quadratic amount of space to store, and so you are better off using the adjacency matrix for $O(1)$ edge queries. There are other trade-offs that one can consider as well depending on the queries you anticipate using often, such as vertex insertion/deletion, neighborhood queries, among others... but this is the general rule of thumb.

It may also make a difference when implementing certain algorithms, like Dijkstra's. Using an adjacency matrix, the algorithm takes $O(|V|^2)$ time, but using an adjacency list, it can be implemented in $O(|V| + |E| \log |E|)$ time. This type of trade-off is common when implementing different graph algorithms.

• You are right, that should have been $\Theta$. And as i've stated, these are not really rules that cover the whole spectrum, but rather just common terminology. I've have seen graphs referenced this way in several courses and textbooks. – user340082710 Mar 17 '16 at 14:41
• From wikipedia: "In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph." From what I have seen, here 'a few' means $O(|V|)$. – user340082710 Mar 17 '16 at 14:43
• I reject Wikipedia as reference in places where it matters. That said, it doesn't seem to be a fixed notion. – Raphael Mar 17 '16 at 18:47

An adjancency matrix takes up more space, the size is not flexible with repect the the number of element. Given that you have 20 vertices with only few just being connect, when represented with an adjacency list, its still take up the same (approximately the same space).

So its only resonable to use the matrix when you are sure you will be using a reasonable size of the already allocated space. For Adjacency List, its dyanamic and space increase as number of the vertex grows, So, its best to just use adjacency list for small sparse graph.