algorithm to untangle a graph

[grasp06110]

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

 

[alexandre_paterson]

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

 

[chris brat]

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

 

[bugbear]

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.

Read some of the background stuff here:

http://www.graphviz.org/

BugBear

 

[grasp06110]

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