[MAJOR] Beyond Force-Directed Layout

[matthew-piziak]

Ah, the mysteries of graph layout. Once upon a time I found a mistakenly sent email in my work account that contained nothing but a reference to a three-hundred page textbook called Planar Graph Drawing, filled entirely with techniques for prettily rendering planar graphs. That was not the beginning of my fascination with graphs, but it was a reminder that the problem of placing nodes and edges upon our two-dimensional retinas is a non-trivial problem with great potential for artistry and clarity.

Of course, our Org Roam databases are not planar. Or maybe yours are, but I can see that for my graph the edges have to cross somewhere. So the problem is even more sophisticated than the one described by that textbook. In the interests of starting the conversation, which should be interesting even on its own, I'd like to describe here some potential alternatives to the current force-directed graphing algorithm. This is all highly speculative, but I'm hoping to hear the perspective of users who may have experience with other ways of doing graph layout.

The Status Quo: Force-Directed Drawing

The current algorithm for Org Roam UI is the Force-Directed Graph Drawing. The algorithm doesn't care too much about the global structure of the graph, so it can place the nodes and pull them by their edges until they settle. This tends to provide a nice spacial uniformity to the graph, relatively equal-ledge edges. It's also fast, intuitive, and good for interactivity, since adding a note just jiggles the graph a bit rather than globally changing its layout.

Spectral Layout

Spectral layout is faster still than force-directed drawing. It uses the full adjacency matrix of nodes to calculate their positions.

Now, the trick here is that you can use spectral layout as a starting point for the nodes, and let force-direction take it from there. That way you have a more attractive arrangement, but you retain all the intuitiveness and user-interactivity of the force-directed layout. I think of it as force-direction finding something closer to the global optimum, thanks to the initial spectral layout.

Orthogonal Layout

I have less familiarity with these layouts, but they have the advantage that the graph will be aligned with node labels.

Getting more perspective

First of all, I don't know if it's even possible to get layouts that are meaningfully better than what Org Roam UI already offers by default. I would love to know if someone has experience playing with different layouts on large graphs, and if they've found substantially better readability or insight with other algorithms. There's no point in implementing an algorithm if we don't even know if it will be better.

The Org Roam database contains an adjacency list, so if any other program has the ability to import, then we could use it to trial alternative layouts.

Resources

• Spectral Graph Layout
• data visualization - List of graph layout algorithms - Cross Validated
• yEd - Graph Editor (I might be able to export Org Roam's adjacency matrix to Excel, and thence to yEd, to experiment with its layout algorithms.)
• Matrix Market
• {1807.09368} Graph Compact Orthogonal Layout Algorithm
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs