algorithm to untangle a graph

04-18-06, 02:07 PM

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

04-18-06, 03:39 PM

alexandre_paterson

Hi,

grasp06110 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
- 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-tutor...onstraints.pdf

04-18-06, 04:05 PM

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

04-18-06, 04:22 PM

bugbear

grasp06110 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

04-18-06, 08:47 PM

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

Similar Threads
O.T. Anyone Purchase a Untangle Device? or Use Untangle? I'm thinking of going back to Linux on a PC for Firewalls (I know what you are saying) But I remember using Smoothwall and thinking wow this is cool. I have yet to set up a...
Graph reduction algorithm Dear group, I have a directed cyclic graph G1, such that each arc holds information over which there exists an equivalence relation C. The nodes hold no information. I...
graph layout algorithm Hello, I am looking for graph layout algorithms. I am representing a process flow using a graph. I have the visual representation of nodes and connectors. I would like to...
Graph algorithm Hi, I have a question about graph algorithm. Given a graph and two nodes s and t, how to find all the shortest paths between s and t? Thanks.
Graph Algorithm Question Hi Folks, Given a directed graph, is there an algorithm to do the following: 1) Shortest path: the answer is simple. dijkstra algorithm. 2) Given a directed graph, and...