10
$\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$
3
  • 2
    $\begingroup$ Circle packings are often used for this. See in particular the Generalizations section. $\endgroup$ May 8, 2019 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$ May 8, 2019 at 20:31
  • $\begingroup$ Another reference: Perry, Scott, Mason Sun Yin, Kathryn Gray, and Stephen Kobourov. "Drawing graphs on the sphere." In Proceedings of the International Conference on Advanced Visual Interfaces, pp. 1-9. 2020. $\endgroup$ Sep 9, 2022 at 16:22

2 Answers 2

8
$\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$
8
  • $\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$ May 8, 2019 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$ May 8, 2019 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, 2019 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$ May 8, 2019 at 16:01
  • 3
    $\begingroup$ This is actually implemented in Mathematica as GraphLayout -> "SpectralEmbedding". $\endgroup$ May 8, 2019 at 16:20
3
$\begingroup$

I am working on this, work in progress. Algorithm determines a separating circle and maps that onto 4 spherical edges of 6 of unit sphere tetrahedron. Basically Tutte algorithm on polar coordinates is used twice, with separating circle as "outer face". No problem for vertical angles [0°..180°], but horizontal angles [0°..360°) have overlap problem. I solved that by forcing separating circle angles to [0°..270°] for left side of separating circle vertices, and use Tutte algorithm for that. Then I add 360° to vertices with horizontal angles [0°..90°], which results in angles [180°..450°], and use Tutte algorithm for right side of separating circle vertices. Here is an example embedding of C36.10 fullerene (10th of 15 non-isomorphic C36 fullerenes generated with plantri52):
enter image description here

More details here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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