# Chapter 4. Graph Representations

# 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:

```text
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:

```text
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.