Equalizing edge lengths in simple graphs

I would like to generate a graph from an adjacency matrix in which each edge of the graph is forced to be the same length. The specific length of the edges is not important and could be any value (i.e. 1cm) as long as such a value results in a graph that can be easily understood, for example, edges that are too short may result in vertices being too close together and this may make the graph look "cluttered"

All input matrices are simple, square adjacency matrices and an example of one (19 x 19) is as follows:

A = [0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0]

The idea here is that certain graphs (with a particular number of vertices of specific degree) cannot exist when all edges are forced to be exactly equal in length. Furthermore, certain graphs will be forced into specific geometries once all edges are forced to be equal in length. These are the things I am interested in.

This seems like a relatively simple process but graphs typically contain only topological properties (i.e. vertex connectivities) not geometrical properties such as edge lengths and thus I am not sure how to write code for this problem.

Please let me know if anyone has any ideas !

Thank you

Answer 1

[Aashray]

Hello @Maxwell Day!

This is a really interesting problem, since it involves moving beyond the usual topological representation of graphs and enforcing geometric constraints, requiring that all edges be of equal length.

To achieve this, I took an optimization-based approach:

1. Treat the node positions in 3D space as optimization variables.
2. Define an objective function that penalizes the difference between the actual length of each edge and the target length (which is set to 1 unit).
3. Add a slight encouragement for variance along the Z-axis to help "spread out" the graph in 3D and reduce overlap.
4. Use MATLAB's “fminunc” to minimize this objective function and find possible 3D positions.
5. In the end, add a verification step to check whether all edge lengths fall within a reasonable tolerance (±2%). If any edge deviates more than that, flag it and skip plotting.

This is the code I wrote:

function equal_length_graph_3d(A)
% Performing preliminary checks on the input
if ~isequal(A, A') || any(diag(A))
    error('Input must be a symmetric, zero-diagonal adjacency matrix.');
end

n = size(A, 1);
[r, c] = find(triu(A));
edges = [r, c];
m = size(edges, 1);

% Initial random 3D positions for nodes
X0 = randn(n * 3, 1);

% Objective function with a Z-spread encouragement (in order to avoid
% clustering of nodes)
    function cost = energy(X)
        X = reshape(X, 3, [])';
        edge_cost = 0;
        for k = 1:m
            i = edges(k, 1);
            j = edges(k, 2);
            d = norm(X(i, :) - X(j, :));
            edge_cost = edge_cost + (d - 1)^2;
        end
        varZ = var(X(:,3));
        dim_cost = -1e-2 * varZ;
        cost = edge_cost + dim_cost;
    end

% Optimization
options = optimoptions('fminunc', 'Algorithm', 'quasi-newton', ...
    'MaxIterations', 1000, 'Display', 'off');
Xopt = fminunc(@energy, X0, options);
Xopt = reshape(Xopt, 3, [])';

% Distance Check 
tolerance = 0.02; % allowing 2% deviation in edge lenghts (Maxwell, you
% may reduce it if you want exactly equal edges).
valid = true;
for k = 1:m
    i = edges(k,1);
    j = edges(k,2);
    d = norm(Xopt(i,:) - Xopt(j,:));
    if abs(d - 1) > tolerance
        fprintf('Edge (%d,%d) has length %.3f, which exceeds tolerance.\n', i, j, d);
        valid = false;
    end
end

if ~valid
    fprintf('Graph NOT plotted because not all edge lengths are within tolerance (±%.2f).\n', tolerance);
    return;
end

% Plotting
figure; hold on; axis equal;
for k = 1:m
    i = edges(k,1); j = edges(k,2);
    plot3([Xopt(i,1), Xopt(j,1)], ...
        [Xopt(i,2), Xopt(j,2)], ...
        [Xopt(i,3), Xopt(j,3)], ...
        'b-', 'LineWidth', 2);
end
scatter3(Xopt(:,1), Xopt(:,2), Xopt(:,3), 100, 'k', 'filled');
title('3D Graph with Equal Edge Lengths');
xlabel('X'); ylabel('Y'); zlabel('Z');
view(30, 25);
end

You can call the function by supplying a valid adjacency matrix representing a graph as input.

I tried this code on multiple graphs, attaching some of the plots with their corresponding adjacency matrices for you to get a better idea.

A = [0, 1, 1, 1;
         1, 0, 1, 1;
         1, 1, 0, 1;
         1, 1, 1, 0];
    equal_length_graph_3d(A)

    A = [0, 1, 1, 1, 1;
        1, 0, 1, 1, 1;
        1, 1, 0, 1, 1;
        1, 1, 1, 0, 1;
        1, 1, 1, 1, 0];
    equal_length_graph_3d(A)

Edge (1,2) has length 0.886, which exceeds tolerance.
Edge (1,3) has length 1.094, which exceeds tolerance.
Edge (2,3) has length 0.885, which exceeds tolerance.
Edge (1,4) has length 0.886, which exceeds tolerance.
Edge (2,4) has length 1.242, which exceeds tolerance.
Edge (3,4) has length 0.886, which exceeds tolerance.
Edge (1,5) has length 1.094, which exceeds tolerance.
Edge (2,5) has length 0.885, which exceeds tolerance.
Edge (3,5) has length 1.094, which exceeds tolerance.
Edge (4,5) has length 0.886, which exceeds tolerance.
Graph NOT plotted because not all edge lengths are within tolerance (±0.02).

For the adjacency matrix you have shared in the question:

I am also attaching the documentation link for the “fminunc” function for reference: https://www.mathworks.com/help/optim/ug/fminunc.html