7
$\begingroup$

If I have a graph of a reasonable size (e.g. ~100 nodes, ~40 edges coming out of each node) and I want to represent it in R^3 (i.e. map each node to a point in R^3 and draw a straight line between any two nodes which are connected in the original graph) in a way which would make it easy to understand its structure, what do you think would make a good drawing criterion?

I know this question is ill-posed; it's not objective. The idea behind it is easier to understand with an extreme case. Suppose you have a connected graph in which each node connects to two and only two other nodes, except for two nodes which only connect to one other node. It's not difficult to see that this graph, when drawn in R^3, can be drawn as a straight line (with nodes sprinkled over the line). Nevertheless, it is possible to draw it in a way which makes it almost impossible to see its very simple structure, e.g. by "twisting" it as much as possible around some fixed point in R^3. So, for this simple case, it's clear that a simple 3D representation is that of a straight line. However, it is not clear what this simplicity property is in the general case.

So, the question is: how would you define this simplicity property?

I'm happy with any kind of answer, be it a definition of "simplicity" computable for graphs, or a greedy approximated algorithm which transforms graphs and that converges to "simpler" 3D representations.

Thanks!

EDITED

In the mean time I've put force-based graph drawing ideas into practice and wrote a computer program to simulate how imposing an electrical repulsive force between nodes (Coulomb's Law) and a spring-like behaviour on edges (Hooke's law) would turn out. I've posted the video on youtube. The video starts by randomly generating a graph of 100 nodes each with approximately 1-2 outgoing edges, placing the nodes randomly in 3D space. Then all the forces I mentioned are put into place and the system is left to move around subject to those forces. In the beginning, the graph is a mess and it's very difficult to see the structure. Closer to the end, it is clear that the graph is almost linear. I've also experience with larger-sized graphs but sometimes the geometry of the graph is just a mess and no matter how you plot it, you won't be able to visualise anything. And here is an even more extreme example with 500 nodes.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ One standard algorithm constructs such a "representation of the graph in $\mathbb{R}^3$" using the first 3 eigenvectors of a weighting of the graph's adjacency matrix. With this representation, the distance between vertices A and B is an approximate measure of the "number" of "short" random walks between A and B. For details see, eg., pnas.org/content/102/21/7426 by Coifman-Lafon-Lee-Maggioni-Nadler-Warner-Zucker. $\endgroup$
    – macbeth
    Commented Feb 15, 2011 at 3:37

6 Answers 6

Reset to default
9
$\begingroup$

You might start by exploring the various tools that are available. For example, Mathematica's GraphPlot3D[] does a nice job with small graphs. Here is a 5-node graph:
      Graph 3D
And here is a somewhat dense 50-node graph:
      Graph Random 50

Both were produced without giving Mathematica any advice. Like most such tools, it has options for applying different methods, e.g., SpringEmbedding.

Edit. As requested by Surikator, here are some random, more-sparse, 50-node graphs:
Sparse graphs

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is interesting. I would be very interested to see what Mathematica draws if the 50 node graph you have there has only a couple of edges coming out of each node. (See my video link in the edited question.) Very dense graphs (many edges) will always be hard to visualise but some sparser graphs (fewer edges) are those which can gain most from a clever displacement of the nodes. Unfortunately, although it's great to see graphs drawn by Mathematica, we have no idea about the algorithm used to draw them. $\endgroup$
    – Surikator
    Commented Feb 15, 2011 at 23:20
  • $\begingroup$ @Surikator: Here are some quotes from the documentation: "Possible settings for Method include "SpiralEmbedding", "RandomEmbedding", "HighDimensionalEmbedding", "RadialDrawing", "SpringEmbedding" and "SpringElectricalEmbedding". With Method->Automatic, GraphPlot3D normally uses the "SpringElectricalEmbedding" method, though it uses the "RadialDrawing" method if the graph is a tree." My images were drawn by the default SpringElectricalEmbedding, which balances two forces, one attractive one repulsive, by minimizing an energy. It is defined precisely in the documentation. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 15, 2011 at 23:55
  • $\begingroup$ @Joseph Nice! So, they're also using force-based graph drawing, possibly similarly to the wikipedia link I posted in the comment to Jim and to what I actually implemented and illustrated in the video. Good to know. Thanks! $\endgroup$
    – Surikator
    Commented Feb 16, 2011 at 0:05
4
$\begingroup$

There is a vast literature on Graph Drawing (mostly in two dimensions, but a lot of ideas can be extended to three). The first paper in the subject (almost exactly fifty years ago) was W. Tutte's "How to draw a graph", where the idea was that if you fixed some vertices to be the vertices of a convex polygon, you can make the other vertices satisfy the condition that every vertex is the barycenter of its neighbors. Most of that paper is devoted to a completely incomprehensible argument to show that such drawings are actual embeddings (so no pair of edges crosses) -- this has been reproved (or proved, depending on how cynical you are) by a number of people. That issue does not really arise in three dimensions, however. The Tutte embeddings (which have been generalized in various ways) are discrete harmonic maps.

Improve this answer
$\endgroup$
2
$\begingroup$

I'll mention this since no-one else has. Maple did it in the deprecated network package and now does it in the plots package as graphplot3d : Make the adjacency matrix of the graph. Then the graphplot3d command will do the following: find three eigenvectors (maybe of unit length) by default for eigenvalues 2,3,4 although you can choose. This give 3 vectors in $\mathbb{R}^n$ It will view them as $n$ triples in $\mathbb{R}^3$ and use these as the vertex locations. Sometimes it works nicely showing off symmetries, other times not so well. Some documentation

I am not praising Maple here rather the method. Below are 3 plots of random sparse 50 vertex graphs. I'd like thicker edges and cute balls at vertices. Also I had to fool around a bit to not have a number at each vertex.

The springs method is nice, and you can probably nudge and shake or pull and release to see what happens. At least in Maple the system of differential equations can start to really bog down for a big graph. I like that the representation by this eigenvalue method is completely determined by the graph. The results can be quite nice, when it works. I tried the Hoffman Singleton Graph (50 vertices, regular of degree 7) and none of the eigenvector choices I made came out with a nice graph. 3 graphs http://www.freeimagehosting.net/uploads/2c7605e986.jpg

Improve this answer
$\endgroup$
1
$\begingroup$

An idea that occurred to me, though I don't know how computationally feasible it is, is to insist all edges are of length one [Edit: this can't be done in general.], put a repelling charge on each vertex, and let the graph float to an equilibrium position. This would be somewhat analogous to the idea of minimizing "knot energy" in the case of embeddings of $S^1$ in $\mathbb R^3$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Insisting each edge has length one can be tricky. After you have drawn a lot of nodes, it will become difficult to choose the position of the next node in such a way that the distance to all the other nodes it connects to is one. I mean, how would you determine the initial position of the nodes before repelling forces come into place? Or am I missing something? $\endgroup$
    – Surikator
    Commented Feb 15, 2011 at 2:46
  • 4
    $\begingroup$ You can't require all edges to have the same length for an embedding into $\mathbb{R}^3$. There's no way to embed $K_5$, for example. $\endgroup$
    – Chris Eagle
    Commented Feb 15, 2011 at 2:53
  • 1
    $\begingroup$ I have also been pointed to en.wikipedia.org/wiki/… which follows the repelling charge and equilibrium positions you mention. $\endgroup$
    – Surikator
    Commented Feb 15, 2011 at 2:53
  • $\begingroup$ @Surikator: thanks for the link. I knew it was an obvious idea... $\endgroup$
    – Jim Conant
    Commented Feb 15, 2011 at 13:05
  • 1
    $\begingroup$ @Jim I've put these ideas into a program that simulates graph behaviour subject to repelling charge forces and spring-like behaviour. See my edit above. Note that if we only impose repelling charge forces, the graph will explode (literally). That's why you were trying to keep the edges at constant unit length. Although that is not possible, a nice approximation to that is to choose some random lengths and say that the lengths should not vary much from those initial lengths -- that can be achieved by giving them spring-like behaviour, i.e. a force preventing the edges from becoming too long. $\endgroup$
    – Surikator
    Commented Feb 15, 2011 at 23:26
0
$\begingroup$

complexity(graph,f) := $\displaystyle\sum_{\langle g,r\rangle \in \; \operatorname{graph}^2} \begin{cases} 0 & \text{if }g=r \\\\ \operatorname{log}\left(\frac{d(f(g),f(r))}{d(g,r)}\right)^2 & \operatorname{if }g\neq r\end{cases}$

although I suppose this is more quality of embedding than simplicity ...

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Where does this definition come from? $\endgroup$
    – Igor Rivin
    Commented Feb 15, 2011 at 2:34
  • $\begingroup$ What is f and what is the definition of d (which I suppose is a distance)? $\endgroup$
    – Surikator
    Commented Feb 15, 2011 at 2:49
  • $\begingroup$ This definition comes from my having seen it somewhere (I forget where) as a measure for map projections. f is the embedding, d is the distance between either vertices or points in R^3, depending on what its inputs are. $\endgroup$
    – user5810
    Commented Feb 15, 2011 at 4:35
0
$\begingroup$

A truncated icosahedron can be embedded in a plane, but is more symmetrical and easier to understand when embedded in a sphere. This goes for all the Platonic figures and their truncated, rectified, etc. derivatives.

That doesn't really answer the question "what do you think would make a good drawing criterion?" Ok, having a symmetrical embedding in R^3 makes a good drawing criterion.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .