# algorithm to untangle a graph

Discussion in 'Java' started by grasp06110@yahoo.com, Apr 18, 2006.

1. ### Guest

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

, Apr 18, 2006

2. ### Guest

Hi,

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:

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

, Apr 18, 2006

3. ### chris bratGuest

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

chris brat, Apr 18, 2006
4. ### bugbearGuest

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

bugbear, Apr 18, 2006
5. ### Guest

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

, Apr 18, 2006