Force-directed graph drawing in 1D?

I think this question might be better for one of the computer science StackExchange sites.

In any case, the literal answer to your question is No. The trouble is that in a conventional force-directed layout algorithm, repulsive forces between nodes become arbitrarily high as the nodes become close. As a result, nodes can't "pass through" each other. That's not a problem in 2D (they can pass around each other) but in 1D it means your layout is essentially stuck with the initial position, since there's no way for the ordering to change.

Instead, you might try spectral layout methods, which are quite elegant. You could also simply do a 2D layout and project to one dimension. Or you could try a version of the usual force-directed algorithms that avoids high repulsive forces.


As an alternative to force-directed layout, you might investigate the MinLA problem: the minimum linear arrangement problem for nodes on a line. It plays a role in VLSI design. It is NP-hard but there are good approximation algorithms. Here is one paper that will lead to many others:

Yehuda Koren and David Harel. "A Multi-Scale Algorithm for the Linear Arrangement Problem." Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2002. (ACM link)

From its Introduction:


Introduction