Ask HN: Dense Tree Layout Algorithms

These graphs look very much hand-tuned.

Shouldn't the domain be called "Automated Graph Drawing"?

The paper for "Space-Reclaiming Icicle Plot (2020)" looks like it's going into the right direction. A space-reclaiming tree layout would be even better.

For this particular example, I feel like a combination of both human input + algo could work. Something like:

* Have graphviz or some other solver output the [x;y] pairs for each vertex.

* Use the initial positions to create, with a physics engine, a construct where vertices are masses connected by springs following the DAG.

* Add a resizable bounding box constraint around the whole thing.

* Push and pull the boundaries and masses until you get something nice.

What you say still applies: you may want to give the user the ability to resize the masses and re-run the layout algorithm, etc.

The choice and design of algorithm can itself be an aesthetic decision. Eg, OP generated some layouts, and spotted something that wasn't to their taste; the edges frequently overlap. So, we might approach the problem like this:

1. Choose an arbitrary algorithm to lay out trees where the edges don't overlap. There's many ways to do this, it doesn't need to be legible at this step.

2. Insert additional nodes along each edge. How many nodes is a tuning parameter we'll need to play with.

3. Use a traditional force-based graph layout algorithm, one that assigns charge to the nodes so that they repel each other. Because we've given the edges some nodes, they will have charge and won't bunch up together.

4. (Optional?) Detect edge overlaps. If they exist, randomize the initial state and try again.

(Note that the algorithm I've described is O(n^2). Patience will be necessary. You can probably refine it further, I only thought about it for a few minutes. Optimizations applied to physics engines (collision detection, gravity simulation) will apply.)

I've dabbled in generative art like this, and if you're willing to do the math and programming and iterate on the design, you can definitely get something of the aesthetic you are after. Bonus, the skills are transferrable to some other kinds of programming, like property testing and graphics.

> but an algorithm cannot make aesthetic decisions

A constraint or score based process can be given rules for what bad aesthetic decisions are, like nodes too packed in one area, lines between nodes too long, edges shouldn't cross or if that is unavoidable should cross as little as possible, etc, so it can try to avoid them. The process of picking a more optimal solution by judging against these rules might be to apply some randomness and rerun many times, picking the best scoring result, or it might be by moving things around randomly from one start position to see if that improves the score, or both these methods can be applied. Without random factors in the main placement algorithm, reordering how nodes that have no particular precedence (say you have a node with three children that have no property indicating any of them should be ordered/positioned in any particular way with respect to the others visually), reordering how these nodes are passed to some layout functions can have a significant effect, again to be judged against the rules/constraints/scores specified.

This won't be perfect for all inputs, or even many inputs, but it can often produce a good enough result to be made perfect with a bit of human post-processing.

I've definitely seen a demo of this sort of process bing used interactively to layout mind-map drawings, though irritatingly I can't find it ATM to link to. In that the base algorithm ran a few processes, picked one of the results, and from there the human could pull things around, and it had a few controls for how other nodes could be moved in response to any change you made, or if it just warned that parts or the whole might benefit from reflow, or if it blocked the user from making certain changes, or if it stepped back completely at this point and let the user have full control with no further assistance. Of course this might be overkill most of the time: letting the algorithm do the first cut then giving the human full control of post-process tweaks is usually going to be sufficient.

> you do it by hand when you care and with a computer when you are meeting a specification

And for a compromise third option: let the computer do the initial leg work, leave it alone if that result is good enough, and change by hand to refine otherwise.