Chapter 4. Graph Representations

A graph is an abstract object. To compute with it, draw it, store it, or communicate it, one must choose a representation.

A representation is a concrete encoding of the vertex set and edge set. It may be a drawing, a list of edges, an adjacency list, a matrix, or a data structure in memory. The representation is not the graph itself. Different representations may describe the same graph.

The main representations are:

Representation	Best use
Drawing	Human intuition
Edge list	Simple storage and input format
Adjacency list	Traversal and sparse graphs
Adjacency matrix	Fast adjacency queries and algebraic methods
Incidence matrix	Vertex-edge incidence and flow-style arguments

4.1 Drawings

A drawing represents vertices as points and edges as curves or line segments between points.

For example, the graph

V = \{a,b,c,d\}

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\}

may be drawn as a square, a diamond, or two crossing diagonals depending on where the vertices are placed.

The drawing is only a visual representation. It may suggest structure, but it may also mislead. Two drawings can look different while representing the same graph.

Graph theory usually treats graphs abstractly. The exact positions of vertices and the shapes of edges matter only in special subjects such as planar graph theory, geometric graph theory, and graph drawing.

4.2 Edge Lists

An edge list stores the graph by listing its edges.

For the graph

V = \{a,b,c,d\}

with

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\},

the edge list is

(a,b), (a,c), (b,d), (c,d).

For an undirected graph, the pair $(a,b)$ in an edge list usually represents the unordered edge $\{a,b\}$ . The notation is convenient for storage.

An edge list is compact and simple. It is often used in input files, streaming systems, graph databases, and distributed processing. It directly records the edges, and it does not require a fixed vertex ordering unless later converted into a matrix.

The main weakness is adjacency lookup. To decide whether $u$ and $v$ are adjacent, one may need to scan the list.

4.3 Adjacency Lists

An adjacency list stores, for each vertex, the list of its neighbors.

For the graph

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\},

the adjacency list is:

Vertex	Neighbors
$a$	$b,c$
$b$	$a,d$
$c$	$a,d$
$d$	$b,c$

In an undirected graph, each edge appears twice in the adjacency list: once for each endpoint. The edge $\{a,b\}$ appears in the list for $a$ and in the list for $b$ .

Adjacency lists are natural for graph traversal. To explore from a vertex $v$ , one reads the list $N(v)$ . This makes adjacency lists well suited for breadth-first search, depth-first search, connected components, shortest paths on sparse graphs, and many network algorithms.

For a graph with $n$ vertices and $m$ edges, an adjacency list uses space proportional to

n + m.

This is efficient when the graph is sparse. A sparse graph has relatively few edges compared with the maximum possible number of edges. Standard algorithm texts contrast this with the $n^2$ storage used by adjacency matrices.

4.4 Adjacency Matrices

An adjacency matrix represents a graph by a square matrix.

Let

V = \{v_1,v_2,\ldots,v_n\}

be an ordered vertex set. The adjacency matrix of a simple graph $G$ is the $n \times n$ matrix $A$ defined by

A_{ij} = \begin{cases} 1, & \text{if } \{v_i,v_j\} \in E(G), \\ 0, & \text{otherwise.} \end{cases}

For the graph with vertex order $a,b,c,d$ and edge set

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\},

the adjacency matrix is

A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}.

The matrix is symmetric because the graph is undirected. Also, the diagonal entries are zero because the graph has no loops. These are standard properties of adjacency matrices for finite simple undirected graphs.

4.5 Matrix Entries

The entry $A_{ij}$ records adjacency between $v_i$ and $v_j$ .

For a simple graph,

A_{ij} \in \{0,1\}.

For a multigraph, the entry may count the number of edges between $v_i$ and $v_j$ .

For a directed graph, the entry $A_{ij}$ records an edge from $v_i$ to $v_j$ . The matrix need not be symmetric, since an edge from $v_i$ to $v_j$ need not be accompanied by an edge from $v_j$ to $v_i$ .

For a weighted graph, the entry may store the weight of the edge. If no edge exists, one often stores $0$ , $\infty$ , or a special missing value, depending on the algorithm.

Graph type	Meaning of $A_{ij}$
Simple undirected graph	$1$ if $v_i$ is adjacent to $v_j$ , else $0$
Directed graph	$1$ if there is an arc $v_i \to v_j$ , else $0$
Multigraph	Number of edges between the vertices
Weighted graph	Weight or cost of the edge

4.6 Advantages of Adjacency Matrices

Adjacency matrices support fast adjacency tests.

If the graph is stored as a matrix, one can check whether $v_i$ and $v_j$ are adjacent by reading the single entry

A_{ij}.

This takes constant time in a standard array representation.

Adjacency matrices are also useful for algebraic graph theory. Matrix operations can reveal walks, spectra, connectivity, and structural properties. For example, powers of the adjacency matrix count walks in a graph. This fact will be developed later.

The main cost is storage. An adjacency matrix for $n$ vertices stores $n^2$ entries, even when the graph has few edges. Thus adjacency matrices are natural for dense graphs and algebraic methods, but inefficient for very sparse graphs.

4.7 Incidence Matrices

An incidence matrix records the relation between vertices and edges.

Let

V = \{v_1,\ldots,v_n\}

and

E = \{e_1,\ldots,e_m\}.

The incidence matrix is an $n \times m$ matrix $B$ . Its rows correspond to vertices, and its columns correspond to edges.

For an undirected simple graph,

B_{ij} = \begin{cases} 1, & \text{if } v_i \text{ is incident with } e_j, \\ 0, & \text{otherwise.} \end{cases}

For example, let

V = \{a,b,c\}

and

E = \{e_1,e_2\}

where

e_1 = \{a,b\}, \qquad e_2 = \{b,c\}.

With vertex order $a,b,c$ and edge order $e_1,e_2$ , the incidence matrix is

B = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}.

Each column has two $1$ ’s because each edge has two endpoints.

Incidence matrices differ from adjacency matrices. An adjacency matrix records vertex-vertex relations. An incidence matrix records vertex-edge relations.

4.8 Oriented Incidence Matrices

For directed graphs, incidence matrices often use signs.

Let $e_j$ be an arc from $u$ to $v$ . The oriented incidence matrix may use

B_{ij} = \begin{cases} -1, & \text{if } v_i \text{ is the tail of } e_j, \\ 1, & \text{if } v_i \text{ is the head of } e_j, \\ 0, & \text{otherwise.} \end{cases}

Some authors reverse the signs. The choice is conventional. What matters is consistency.

For the directed edges

e_1 = (a,b), \qquad e_2 = (b,c),

with vertices ordered as $a,b,c$ , one convention gives

B = \begin{bmatrix} -1 & 0 \\ 1 & -1 \\ 0 & 1 \end{bmatrix}.

This representation is important in network flows, electrical networks, algebraic graph theory, and discrete differential operators.

4.9 Adjacency Maps

In computer programs, an adjacency list is often implemented as an adjacency map.

For example, a graph may be stored as a map from vertices to neighbor sets:

a -> {b, c}
b -> {a, d}
c -> {a, d}
d -> {b, c}

This representation makes it easy to support arbitrary vertex labels. The vertices do not have to be integers from $0$ to $n-1$ .

A map from vertices to sets supports efficient neighbor iteration and, depending on the set implementation, efficient adjacency testing.

For weighted graphs, each neighbor may carry an edge value:

a -> {(b, 7), (c, 2)}
b -> {(a, 7), (d, 4)}
c -> {(a, 2), (d, 5)}
d -> {(b, 4), (c, 5)}

This is the standard practical form used in many graph algorithms.

4.10 Comparison of Representations

No representation is best for all tasks.

Representation	Space	Fast adjacency test	Fast neighbor iteration	Good for
Edge list	$O(m)$	No	No	Input, streaming, simple storage
Adjacency list	$O(n+m)$	Sometimes	Yes	Sparse graphs, traversal
Adjacency matrix	$O(n^2)$	Yes	No for sparse graphs	Dense graphs, algebraic methods
Incidence matrix	$O(nm)$	No	No	Edge-based algebra, flows

Here $n = |V|$ and $m = |E|$ .

Adjacency matrices use $O(n^2)$ space. Adjacency lists use $O(n+m)$ space. This difference becomes decisive for large sparse graphs.

4.11 Sparse and Dense Graphs

A graph on $n$ vertices can have at most

\binom{n}{2}

edges if it is simple and undirected.

A graph is called sparse when $m$ is much smaller than $n^2$ . It is called dense when $m$ is close to $n^2$ .

Sparse graphs favor adjacency lists. Dense graphs may favor adjacency matrices.

For example, a road network is usually sparse: each intersection connects to only a few nearby intersections. A complete graph is dense: each vertex is adjacent to every other vertex.

The choice of representation should follow the expected operations.

4.12 Representation and Algorithms

Different algorithms prefer different representations.

Breadth-first search and depth-first search repeatedly ask for the neighbors of a vertex. Adjacency lists support this directly.

Shortest path algorithms on sparse graphs usually use adjacency lists with edge weights.

Algorithms based on matrix multiplication or eigenvalues require matrix representations.

Algorithms that process one edge at a time, such as sorting edges for Kruskal’s minimum spanning tree algorithm, naturally use edge lists.

Task	Natural representation
Read graph from file	Edge list
Traverse graph	Adjacency list
Check whether one edge exists	Adjacency matrix or adjacency map
Compute eigenvalues	Adjacency matrix or Laplacian matrix
Sort all edges by weight	Edge list
Work with flows and conservation laws	Incidence matrix

Representation is therefore an algorithmic decision, not only a storage decision.

4.13 Example

Let

V = \{1,2,3,4\}

and

E = \{\{1,2\}, \{1,3\}, \{2,4\}, \{3,4\}\}.

The edge list is

(1,2), (1,3), (2,4), (3,4).

The adjacency list is:

Vertex	Neighbors
$1$	$2,3$
$2$	$1,4$
$3$	$1,4$
$4$	$2,3$

The adjacency matrix, using the vertex order $1,2,3,4$ , is

A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}.

If the edge order is

e_1=\{1,2\}, \quad e_2=\{1,3\}, \quad e_3=\{2,4\}, \quad e_4=\{3,4\},

then the incidence matrix is

B = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}.

All four representations describe the same graph.

4.14 Summary

A graph can be represented by a drawing, an edge list, an adjacency list, an adjacency matrix, or an incidence matrix.

Drawings help intuition. Edge lists are simple. Adjacency lists support traversal and sparse graphs. Adjacency matrices support fast adjacency tests and algebraic methods. Incidence matrices record vertex-edge relations and are useful in flow and structural arguments.

The graph is the abstract pair $G=(V,E)$ . A representation is a chosen encoding of that pair. Later algorithms will depend strongly on this choice.