Velocity Reviews > Java > algorithm to untangle a graph

# algorithm to untangle a graph

grasp06110@yahoo.com
Guest
Posts: n/a

 04-18-2006
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@yahoo.fr
Guest
Posts: n/a

 04-18-2006
Hi,

http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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

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

Tutorial on graph drawing here:

http://www.cs.brown.edu/~rt/papers/g...onstraints.pdf

chris brat
Guest
Posts: n/a

 04-18-2006
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
Guest
Posts: n/a

 04-18-2006
(E-Mail Removed) wrote:
> 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@yahoo.com
Guest
Posts: n/a

 04-18-2006
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