Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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, –  Aaron Meyerowitz Jul 10 '13 at 6:29

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


share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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