How to draw a graph

This entry was last updated on August 9th, 2026

For any representation of a graph $G$ in $\mathbb{R}^k$, we can imagine a mapping

$$\rho : V(G) \to \mathbb{R}^k$$

which assigns each vertex of $G$ a position. Since we are dealing with a finite number of points in $G$, we can represent $\rho$ with a matrix $R$.

$$R := \begin{bmatrix} \rule[0.5ex]{2.5em}{0.4pt} & \rho(v_1)^\top & \rule[0.5ex]{2.5em}{0.4pt} \\ \rule[0.5ex]{2.5em}{0.4pt} & \rho(v_2)^\top & \rule[0.5ex]{2.5em}{0.4pt} \\ & \vdots & \\ \rule[0.5ex]{2.5em}{0.4pt} & \rho(v_n)^\top & \rule[0.5ex]{2.5em}{0.4pt} \\ \end{bmatrix} \in \mathbb{R}^{n \times k}$$

We call $\rho$ balanced iff $\mathbf{1}^\top R = 0$. In English, this just means averaging the position of the vertices gives the origin. Informally, we can always translate our graph so the "middle" is on the origin, we can assume all representations we'll work with are balanced. We can also assume that the columns of the matrix are linearly independent, since otherwise we are looking at some lower dimensional subspace, and we could just look at $\mathbb{R}^{lower dim}$.

It's natural to place our vertices where R tells us to and imagine our edges are springs, then check the "stretching" of strings between vertices. We will want to minimize this stretching for a "good" drawing, but also ignore having 0 distance between vertices, as it's (obviously) not a very impressive drawing although it minimizes energy.

To capture the amount of stretching lets define the energy of $\rho$

$$\mathcal{E}(R) = \sum_{\{u,v\} \in E(G)} \left\lVert \rho(u) - \rho(v) \right\rVert^2,$$

where $\lVert \cdot \rVert$ is the Euclidean norm. If we want to allow some springs to matter more than others, we can introduce a weight function

$$w: E(G) \to \mathbb{R}$$

that assigns a weight to each edge uv $\in$ E(G).

So we end up with the updated energy function

$$\mathcal{E}(R) = \sum_{\{u,v\} \in E(G)} w(uv) \left\lVert \rho(u) - \rho(v) \right\rVert^2.$$

Some expansion and book-keeping verifies the following.

Lemma. The energy is a Laplacian quadratic form,

$$\mathcal{E}(R) = \operatorname{tr}(R^\top L R),$$

where $L = D - W$, the weighted degree matrix minus the weighted adjacency matrix, finally bringing out the familiar (weighted) Laplacian.

This identity gives us our main result.

Theorem. Let $G$ be a connected graph of order $n$ (given by $\lambda_2 > 0$) with weighted Laplacian $L$. If $\lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$ are the eigenvalues of $L$, then the minimum energy of a balanced, orthogonal representation $\rho$ of $G$ in $\mathbb{R}^k$ is

$$\min \mathcal{E}(R) = \sum_{i=2}^{k+1} \lambda_i.$$

Proof Sketch. By the lemma we're minimizing $\operatorname{tr}(R^\top L R)$, and for any orthogonal representation this is at least the sum of the smallest that many eigenvalues of $L$.

Since the rows of $L$ sum to zero, $\mathbf{1}$ is the eigenvector for $\lambda_1 = 0$, so gluing it onto a balanced $R \in \mathbb{R}^k$ as an extra column costs 0 energy and hands us a $\mathbb{R}^{k+1}$ representation forcing $\mathcal{E}(R) \ge \lambda_2 + \cdots + \lambda_{k+1}$. Similarly, we can add a $\mathbf{1}$ vector to a minimum representation in $\mathbb{R}^{k-1}$ to get a representation in $\mathbb{R}^k$ with equal energy. $\blacksquare$

If we are drawing a graph on paper or something like $\mathbb{R^2}$, this is $\lambda_2 + \lambda_3$. Finally, this yields our algorithm given a graph G:

1. Compute the two smallest non-zero eigenvalues $\lambda_2 \leq \lambda_3$ of the weighted Laplacian.

2. Compute eigenvectors $u_{2}'$ and $u_{3}'$ for $\lambda_2 \leq \lambda_3$, and normalize to get the unit eigenvectors $u_2$ and $u_3$.

3. This gives $R := [u_2, u_3]$, where each pair $(u_{2i}, u_{3i})$ is a coordinate to be plotted to give drawing.

Example:

10.057

λ₂ + λ₃ = 4.443

2.26× minimum

ShuffleShow spectral layout

Source

C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, 2001.