Tutte embedding (barycentric layout) algorithm for planar graphs in Elixir.
Tutte's embedding theorem states that if a graph is 3-vertex-connected and planar, pinning its outer boundary to a convex polygon and placing every interior node at the average (barycenter) of its neighbors' positions yields a planar layout without any edge crossings.
Rather than solving the large sparse linear system ($Ax = b$) directly via matrix inversion, this module uses Gauss-Seidel relaxation (iterative relaxation), which runs in pure Elixir without native matrix solver libraries.
Mathematical Model
- Boundary Nodes ($V_b$): Pinned to a circle or regular polygon centered at $(c_x, c_y)$ with radius $R$.
- Interior Nodes ($V_i = V \setminus V_b$): Positioned iteratively. For each interior node $u$: $$ x_u = \frac{1}{deg(u)} \sum_{v \in N(u)} x_v $$ $$ y_u = \frac{1}{deg(u)} \sum_{v \in N(u)} y_v $$ where $N(u)$ is the set of neighbors of $u$, and $deg(u)$ is the degree of $u$.
Complexities
- Time Complexity: $O(I \cdot (V + E))$ where $I$ is iterations, $V$ is nodes, $E$ is edges.
- Space Complexity: $O(V)$ auxiliary space.
References
Summary
Functions
Positions nodes using Tutte's barycentric embedding.
Functions
@spec layout(Yog.Graph.t(), [Yog.Graph.node_id()], keyword()) :: %{ required(Yog.Graph.node_id()) => {float(), float()} }
Positions nodes using Tutte's barycentric embedding.
Requires a list of boundary_nodes (ordered) forming the outer convex boundary polygon.
Options
:iterations- Number of relaxation steps to run (default:100).:radius- Bounding boundary radius (default:1.0).:center- Center of boundary circle (default:{0.0, 0.0}).
Examples
iex> graph = Yog.from_unweighted_edges(:undirected, [{1, 2}, {2, 3}, {3, 1}, {1, 4}, {2, 4}, {3, 4}])
iex> pos = Yog.Layout.Tutte.layout(graph, [1, 2, 3])
iex> Map.keys(pos) |> Enum.sort()
[1, 2, 3, 4]