algorithm to untangle a graph

Thread view:

grasp06110@yahoo.com - 18 Apr 2006 14:07 GMT

Hi,

Does anyone know of a good algorithm to untangle a graph? Or to be
more precise: Does anyone know of a good algorithm that will determine
the arrangement of vertices and edges of a graph such that the number
of edges that cross is minimized?

I am thinking I could use a brute force method that would add vertices
in every possible order in every possible region and add in each new
edge for a vertex in every possible order. Would this work? Is there
a more efficient (time and/or space) algorithm?

Any help would be appreciated.

Thanks,
John

Reply to this Message

alexandre_paterson@yahoo.fr - 18 Apr 2006 15:39 GMT

Hi,

> Hi,
>
> Does anyone know of a good algorithm to untangle a graph? Or to be
> more precise: Does anyone know of a good algorithm that will determine
> the arrangement of vertices and edges of a graph such that the number
> of edges that cross is minimized?

This is not a Java related question...

> I am thinking I could use a brute force method that would add vertices
> in every possible order in every possible region and add in each new
> edge for a vertex in every possible order. Would this work? Is there
> a more efficient (time and/or space) algorithm?

Bruce force can work if you have very few vertices/nodes/edges.

You'll be unlikely to find any algorithm that scales well for
"minimizing crossings" is known to be an NP-hard problem.

If your graph is planar there are algorithms to draw it such that
no two edges intersects.

If your graph is non-planar it is known that you can:

- make is temporary scalar by adding "fake" vertices at the crossings
- draw it using some well-known planar-graph drawing algorithm
- remove your dummy vertices

Complexity of this is at least O(n^2 log(n)).

Tutorial on graph drawing here:

www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf

Reply to this Message

grasp06110@yahoo.com - 18 Apr 2006 20:47 GMT

Thanks for the help with this. Regarding you comment that this is not
a Java related question, could you advise on a forum better suited for
this type of question?

Thanks,
John

Reply to this Message

chris brat - 18 Apr 2006 16:05 GMT

There are graphing utilities available which offer a choice of
algorythms - no re-inventing the wheel.

JUNG (Java Universal Network Graph) framework is quite decent.

http://jung.sourceforge.net

Chris

Reply to this Message

bugbear - 18 Apr 2006 16:22 GMT

> Hi,
>
[quoted text clipped - 9 lines]
>
> Any help would be appreciated.

Read some of the background stuff here:

http://www.graphviz.org/

BugBear

Reply to this Message

algorithm to untangle a graph

Free Magazines