7
$\begingroup$

The Tutte embedding is a way to create a "nice" drawing of a 3-connected planar graph in the plane, after having chosen an outer face.

Is there a similar method to draw such a graph on a sphere? Steinitz's theorem suggests that such a drawing is possible.

Of course, we could just map the planar coordinates to a sphere with some arbitrary projection, but this does not produce a "nice" drawing, e.g. it will not reflect the natural symmetries of the graph, and will not produce a dodecahedron for a dodecahedral skeleton. While "nice" is not a very well defined term, I assume there must be some existing work on this topic.

$\endgroup$
  • 2
    $\begingroup$ Circle packings are often used for this. See in particular the Generalizations section. $\endgroup$ – Timothy Budd May 8 at 12:06
  • $\begingroup$ This might help: Aleardi, Luca Castelli, Gaspard Denis, and Eric Fusy. "Fast spherical drawing of triangulations: an experimental study of graph drawing tools." In 17th Internat Symp Experimental Algorithms. 2018. PDF download $\endgroup$ – Joseph O'Rourke May 8 at 20:31
6
$\begingroup$

If the graph $G=(V,E)$ has a lot of symmetries, then using spectral realizations might give you nice drawings that reflects these symmetries. The success of this method (e.g. whether the drawing is planar, whether all vertices are on a sphere) depends on a lot of factors, some of which are not completely clear to me. However, what I can tell you is that it works for the graphs of all uniform 3-polytopes (so, e.g., the dodecahedron).

I explain the most straight forward way to do it, some tweaks might be neccessary for the general case:

Costruction. Let $\theta$ be an eigenvalue of (the adjacency matrix of) $G$, and $v_1,v_2,v_3\in\Bbb R^n$ three ortho-normal eigenvectors to $\theta$. Construct the matrix $M:=(v_1,v_2,v_3)\in\Bbb R^{n\times 3}$ with the $v_i$ as columns. The rows of that matrix are a 3-dimensional embedding of the vertices of $G$.

Usually, you should take $\theta_2$, i.e., the second-largest eigenvalue of the adjacency matrix of $G$. Surprisingly, this eigenvalue has multiplicity three for most symmetric graphs that come from 3-polytopes (exceptions are, as far as I know, only prisms). This means, you cannot do anything wrong by choosing just any orthonormal basis of eigenvectors.

Here is code for Mathematica to automatically find a nice drawing of the dodecahedral graph:

G = GraphData["DodecahedralGraph"];

A = AdjacencyMatrix[G];
n = VertexCount[G];
eval = Eigenvalues[A // N];
th2 = RankedMax[eval, 2];
evec = NullSpace[A - th2*IdentityMatrix[n]];

GraphPlot3D[G,
    VertexCoordinateRules -> Table[i -> evec[[{1,2,3}, i]], {i, 1, n}]
]

Output:

If $\theta_2$ has multiplicity $<3$, you can add eigenvectors of other eigenvalues until you have three, preferably from the next largest eigenvalues. Just do not use the largest eigenvalue.


For your example in the comments (the capped cube), we have the problem that $\theta_2$ has multiplicity one. However, as explained, we could use eigenvectors of $\theta_3$ (which has multiplicity two) to complete to a set of three vectors. Use this:

th2 = RankedMax[eval, 2];
th3 = RankedMax[eval, 3];
evec = NullSpace[A - th2*IdentityMatrix[n]] ~Join~ NullSpace[A - th3*IdentityMatrix[n]];

Output:

For general graphs one should certainly follow a more dynamic approach, e.g. sorting the eigenvectors by their eigenvalues and taking the largest three (but not the largest one). Something like this:

vec = SortBy[Transpose[Eigensystem[A // N]], First][[{-2, -3, -4}, 2]];

GraphPlot3D[G,
    VertexCoordinateRules -> Table[i -> vec[[;; , i]], {i, 1, n}]
]
$\endgroup$
  • $\begingroup$ I was having an awful time to reproduce this at first (before you posted code) because Eigenvalues and Eigenvectors seem to give a different ordering when taking the numericized version of this specific matrix ... Eigensystem is fine though. $\endgroup$ – Szabolcs Horvát May 8 at 13:19
  • 1
    $\begingroup$ It would seem that this works if the graph has a drawing with enough rotational symmetries. That's when there will be an eigenvalue with multiplicity 3. This was the first example that I naively constructed, expecting that your method would not work: i.stack.imgur.com/aJE76.png Call it a box-house with a roof. It turns out that there is an eigenvalue with a multiplicity of 3, and using it leads to this non-obvious drawing: i.stack.imgur.com/1dUqw.png $\endgroup$ – Szabolcs Horvát May 8 at 15:26
  • $\begingroup$ @SzabolcsHorvát I managed to get a decent picture by taking the second and third largest eigenvalue. I extended my answer to include that example. I recommend always taking the largest eigenvalues. $\endgroup$ – M. Winter May 8 at 15:54
  • $\begingroup$ Yes, it does usually work well. layout[g_?GraphQ] := Module[{am = N@AdjacencyMatrix[g], evec, eval, ord}, {eval, evec} = Eigensystem[am]; ord = Reverse@Ordering[eval]; Graph3D[g, VertexCoordinates -> Transpose@Part[evec, Take[ord, {2, 4}]], PlotLabel -> Take[eval[[ord]], 4]] ] then Print@*layout /@ Select[PolyhedronData[#, "Skeleton"] & /@ PolyhedronData[], ConnectedGraphQ] $\endgroup$ – Szabolcs Horvát May 8 at 16:01
  • 3
    $\begingroup$ This is actually implemented in Mathematica as GraphLayout -> "SpectralEmbedding". $\endgroup$ – Szabolcs Horvát May 8 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.