Graph Representation Trade-offs¶

The choice between adjacency matrix (O(1) edge query, O(V^2) space) and adjacency list (O(degree) edge query, O(V+E) space) depends on graph density and operation frequency - sparse graphs favor lists, dense graphs favor matrices.

Tension Addressed¶

Memory Usage vs. Time Performance

Recognizable As¶

Adjacency matrix vs. adjacency list choice; edge list representations; social network storage decisions; any graph database schema design

Canonical Sources¶

Knuth, TAOCP Vol. 1, Section 2.2.1 (1968); Tarjan, Data Structures and Network Algorithms (1983)

Transfers To¶

Social Networks (friend graphs), Geographic Systems (road networks), Dependency Management (package graphs), Knowledge Graphs (semantic networks)

Sub-concepts: - Density threshold: Approximately E > V^2/64 favors matrix representation - Operation profile: Frequent edge existence queries favor matrices; frequent neighbor iteration favors lists