6
$\begingroup$

I have a real-world graph that I wish to draw in one dimension. Here's the graph:

Graph in question

I'd like to draw it using some kind of force-directed graph drawing method. I'm supposing this is both possible and practical, but it may be that there's some obstacle I'm unaware of. So, I'll begin with:

Question: Is 1D force-directed graph drawing possible and practical?

And if so:

Question: Does there exist software for force-directed graph drawing in 1D?

Gephi (among other packages) can provide a force-directed graph drawing in 2D, but I don't believe it can draw in 1D.

(Motivation: I'd like to see how similar the 1D force-directed drawing is to the drawing above, which places the vertices equispaced along the line, and in the order in which they are generated.)

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Force directed does not require Newtonian forces. It would not be against the spirit to say that the repulsive force between unjoined vertices is the smaller of $1$ and $\frac{1}{d^2}$ where $d$ is the distance, so two points could pass through each other . But I agree that it does not seem promising, $\endgroup$ Jul 10, 2013 at 6:29
3
$\begingroup$

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


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.