I was trying to set up a suitable notion of Laplacian matrix for Tutte embeddings of graphs.

Suppose, as usual, we have a graph with $V$ vertices, with $n_v$ being the degree of vertex $v$. Then, the condition is that each vertex be the average of its neighbors. So, each vertex contributes three conditions, i.e., three rows to the constraint matrix. Thus, we end up with a matrix whose number of columns is $3V$, three for each vertex, and likewise for the number of rows. The three rows of our Laplacian contributed by a vertex without positional constraint look as follows: $$ L = \left ( \begin{matrix} \cdots\\ \cdots\\ -1 & 0 & 0 & \cdots & n_v & 0 & 0 & \cdots & -1 & 0 & 0 & \cdots\\ 0 & -1 & 0 & \cdots & 0 & n_v & 0 & \cdots & 0 & -1 & 0 & \cdots\\ 0 & 0 & -1 & \cdots & 0 & 0 & n_v & \cdots & 0 & 0 & 1 & \cdots\\ \cdots \\ \cdots \\ \end{matrix} \right ) $$ In each row, the sum is zero because the $-1$'s add up to $-n_v$. Thus, we are dealing with a singly-stochastic matrix.

However, we need to take care of vertices whose positions are fixed. Such a vertice's three-row block of $L$ looks as follows instead: $$ L = \left ( \begin{matrix} \cdots\\ \cdots\\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 & \cdots\\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 & \cdots\\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 & \cdots\\ \cdots \\ \cdots \\ \end{matrix} \right) $$ and the corresponding three entries of the right-hand side $a$ contain the three fixed coordinates, making the linear system $$ Lx = a $$ inhomogeneous.

Suppose, as usual, we have a graph with $V$ vertices, with $n_v$ being the degree of vertex $v$. Then, the condition is that each vertex be the average of its neighbors. So, each vertex contributes three conditions, i.e., three rows to the constraint matrix. Thus, we end up with a matrix whose number of columns is $3V$, three for each vertex, and likewise for the number of rows. The three rows of our Laplacian contributed by a vertex without positional constraint look as follows: $$ L = \left ( \begin{matrix} \cdots\\ \cdots\\ -1 & 0 & 0 & \cdots & n_v & 0 & 0 & \cdots & -1 & 0 & 0 & \cdots\\ 0 & -1 & 0 & \cdots & 0 & n_v & 0 & \cdots & 0 & -1 & 0 & \cdots\\ 0 & 0 & -1 & \cdots & 0 & 0 & n_v & \cdots & 0 & 0 & 1 & \cdots\\ \cdots \\ \cdots \\ \end{matrix} \right ) $$ In each row, the sum is zero because the $-1$'s add up to $-n_v$. Thus, we are dealing with a singly-stochastic matrix.

However, we need to take care of vertices whose positions are fixed. Such a vertice's three-row block of $L$ looks as follows instead: $$ L = \left ( \begin{matrix} \cdots\\ \cdots\\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 & \cdots\\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 & \cdots\\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 & \cdots\\ \cdots \\ \cdots \\ \end{matrix} \right) $$ and the corresponding three entries of the right-hand side $a$ contain the three fixed coordinates, making the linear system $$ Lx = a $$ inhomogeneous.

And there we are!

Leave a comment here