Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections.

e^n has asked for the wisdom of the Perl Monks concerning the following question:

I have been developing a dynamic, aesthetic map layout system as a web application for users of Eve Online. I am using Graph::Layout::Aesthetic in order to ensure that map coordinates remain as true to the original as possible.

However, I am running into issues with intersections which I am ill prepared to handle. The code initially takes a map similar to this and translates it into this

As you can see, there are several node placements which result in edge intersections which I have highlighted. Graph::Layout::Aesthetic has forces to combat this but they seem to assume the graph is planar which it often isn't. The only solution I have been able to devise so far is the following:

Iterate through every edge
When an intersection is detected determine if any nodes have a degree of 1
If so, move said node to half the distance from it's connected node to the edge it intersected with
If not, iterate through the connected nodes and determine if there is any movement which could reduce intersections.

I came up with a reasonably viable recursive algorithm but could envision no manner of intelligently moving nodes to reduce intersections (anything I tried went crazy).

Essentially what I am looking for is the most efficient way to reduce the number of intersections while keeping the nodes in as close to their original positions as possible. Thanks for your advice!

Comment on Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections.

Replies are listed 'Best First'.
Re: Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections. by Anno (Deacon) on Sep 06, 2007 at 20:33 UTC
The knowledge you are looking for is not Perl-specific, it's graph-specific, even if the language you are using is Perl. I'd look for a graph/graph-represention oriented forum for advice. I'm no expert on graph algorithms (and finding one among the perlmonks would be coincidental), but the problem of minimizing intersections while retaining other properies of a graph representation must have been studied. Anno	[reply]
Re: Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections. by blokhead (Monsignor) on Sep 07, 2007 at 14:47 UTC
Computing the crossing number of a graph (that is, the fewest number of edge intersections needed to draw the graph in the plane) is an NP-complete problem. According to the problem's entry in the compendium of NP-complete problems, there don't appear to be any general approximations either. Ad-hoc heuristics will probably be as good as you can hope for, if you want to be able to handle large, dense graphs efficiently. Also, when I think about aesthetically pleasing graphs, I think of graphviz. It has a lot of sophisticated logic for laying out vertices, yielding nice-looking results. I don't know if it takes edge crossings into account as part of its measure of graph niceness, but it could be worth a look to see if/how they do it. Graphviz does take liberties about rearranging nodes (in general this is necessary to reduce the crossing number of an embedding), so it might not exactly suit your needs.. blokhead	[reply]
Re: Aesthetic map layout using Graph::Layout::Aesthetic and problems with intersections. by SuicideJunkie (Vicar) on Sep 07, 2007 at 14:11 UTC
Something to consider: In reducing intersections while keeping nodes as close to their original positions as possible, what is the importance of each requirement? In your example, you could reduce intersections, but that would require moving some nodes a significant distance. If the minimizing of intersections is not an absolute priority (and given that zero will not be an option if the graph is non-planar), then is it really that bad to have a few intersections if they improve the match to original position? To me, at least, the example graph looks like it could be a reasonable tradeoff.	[reply]