Honestly, I’ve been running a little low on passion for side-projects and true deep dives lately. Lots of reasons, most of which you can probably guess if you also live in the US or work in tech.

But I’m still pretty obsessed with graph layout. Basically I love d3-force - force-directed layout, but I think that it’s used everywhere and isn’t the right choice for everything. And graph layout is catnip to computer scientists so there’s a ton of cool research being written about alternative algorithms.

I think this graph could be better. That’s a real load-bearing could though: Mike’s work on d3 is big for a reason: he focused on and solved a lot of really hard problems that others were scared of.

But on the New York subway, I see their subway maps and I am transfixed. Hand-drawn charts look different than what a computer can generate. Old charts are just amazing.

There are a bunch of things about beautiful charts that I appreciate:

• Orthogonal or semi-orthogonal layouts: all of the edges are horizontal, vertical, or in some cases, diagonal. Subway maps have diagonals and I think it looks amazing. As far as I can tell so far though, most chart implementations are either freeform or orthogonal.’
• Edge bundling. See circuit diagrams. If there are a bunch of edges following similar routes, they should line up and potentially be combined into one.
• Good nodes. For example, subway charts don’t have all of the subway lines pinching together for each station, but instead they show the station as kind of a horizontal joining line.
• Symmetry. It’s human, but it’s pretty nice to see charts that prioritize making things symmetrical, even if that’s not optimal in another direction.

So I’ve been reading some papers.

I liked A Walk On The Wild Side: a Shape-First Methodology for Orthogonal Drawings. Some of the takeways:

• Most orthogonal drawing is based on the Topology-Shape-Metrics paradigm, which tries hard to avoid links crossing over each other.
• Instead, they care more about minimizing bends in the links, which they think looks better and matters more than crossings.
• They do so with a SAT solver (oooh!) so they can defer some of the really hard algorithmic work to that.

But so far my favorite is HOLA: Human-Like Orthogonal Network Layout. The results look spectacular. The gist is:

• Instead of optimizing for something they think is nice, they tested what people would do if they laid out graphs themselves.
• They came up with five criteria for good graphs (trees placed outside, aesthetic bend points, compactness, grid-like node placement, symmetry - though I recommend just looking at the paper because there are good illustrations for these).
• I haven’t read through the implementation but I’m guessing it’s pretty complicated to achieve all of these goals. I think the main implementation is in libdialect. There’s a JavaScript port of sorts called cola.js, which has a gridified example but I don’t think that’s actually HOLA. Also there’s a python implementation of HOLA, but that relies on the C++ adaptograms implementation so I don’t know if it would be any easier to port.
• Bracketing the feelings involved, potentially a TypeScript port of libdialect is possible via LLMs. I suspect that the lack of real integers and the different performance profile might be tricky, though.

Sidenote: when reading through the ogdf documentation I saw that they use earcut, made by Mapbox! Cool to see that foundational work like that is so widely adopted, and liberal open source licensing makes it possible.

HOLA was written in 2015, so I went looking for more recent work, and found Praline which has a Java implementation by the authors.

And then A Simple Pipeline for Orthogonal Graph Drawing, which cites PRALINE and HOLA as examples and has really nice output. I was hopeful that the ‘simple’ in that paper meant that it was simple to implement, which… not sure. There’s a Scala implementation.

It’s amazing to me that some of this really cutting-edge work sits in repositories on GitHub with 6 stars (one of them mine) when they represent so much real thought and effort. Of course the real product is the paper, and the real reward is PhDs, tenure, respect of their peers, and citations. But still!

Then the same authors as "A Simple Pipeline" - Tim Hegemann and Alexander Wolff - wrote Storylines with a Protagonist which as an online demo which implements a lot of the nice parts of subway-map drawing!

I’m having fun following along with fancy graph-drawing algorithms! Some questions that I am looking to answer next:

• If I use an LLM to translate Scala to TypeScript and popularize one of these, am I the baddie? It feels kind of bad to think about it.
• Are force-directed graphs successful because they’re fast and general and that puts a ceiling on these nicer but potentially slower and less general alternatives?
• Do graph drawing algorithms with eight-directional links (diagonals) exist? I can’t figure out what to search for and I haven’t found any evidence that this is supported yet.