Request for Built-in Function: Tutte Embedding of 3-Connected Planar Graphs

[lichengzhang1]

Problem Description

The Tutte embedding is a graph-drawing technique to position vertices of a graph so that the outer face is a convex polygon and each interior vertex is at the mean of the positions of its adjacent vertices.

SageMath does not seem to have it built-in yet.

Proposed Solution

An implementation in sage can be found at tuttedraw due to Manfred Scheucher. Here is the core code for it.

from scipy.spatial import ConvexHull
from sys import argv
from ast import literal_eval
import xml.etree.ElementTree as ET

from scipy import optimize
def tutte_layout(G,outer_face,weights):
	V = G.vertices()
	pos = dict()
	l = len(outer_face)

	a0 = pi/l+pi/2
	for i in range(l):
		ai = a0+pi*2*i/l
		pos[outer_face[i]] = (cos(ai),sin(ai))
	
	n = len(V)
	M = zero_matrix(RR,n,n)
	b = zero_matrix(RR,n,2)

	for i in range(n):
		v = V[i]
		if v in pos:
			M[i,i] = 1
			b[i,0] = pos[v][0]
			b[i,1] = pos[v][1]
		else:
			nv = G.neighbors(v)
			s = 0
			for u in nv:
				j = V.index(u)
				wu = weights[u,v]
				s += wu
				M[i,j] = -wu
			M[i,i] = s

	sol = M.pseudoinverse()*b
	return {V[i]:sol[i] for i in range(n)}




s = 'JsTB@_OBGN?'
G = Graph(s, sparse=True); 
F = G.faces()
F = [tuple(e[0] for e in f) for f in F]	
outer_face=F[0]
weights = dict()
for (u,v) in G.edges(labels=None):
     weights[u,v] = weights[v,u] = 1
G.set_pos(tutte_layout(G,outer_face,weights))
G.plot(edge_thickness=2, vertex_size=150)

Alternatives Considered

1. https://github.com/daryatodoskova/CSE306_TD9
2. https://github.com/DarlingZzzz/Tutte-Embedding

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

[nturillo]

#38762

I added a PR for this