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
    #1
    1. Advertising

  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
    - 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
     
    , Apr 18, 2006
    #2
    1. Advertising

  3. chris brat Guest

    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
    #3
  4. bugbear Guest

    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
    #4
  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
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. iliad
    Replies:
    5
    Views:
    1,516
    iliad
    Sep 21, 2005
  2. George Sakkis
    Replies:
    1
    Views:
    457
    Szabolcs Nagy
    Jan 29, 2007
  3. Dr Ann Huxtable

    Missing Graph.h and (Graph.lib) woes - any help

    Dr Ann Huxtable, Dec 21, 2004, in forum: C Programming
    Replies:
    6
    Views:
    653
    Dr Ann Huxtable
    Dec 21, 2004
  4. Jef Driesen
    Replies:
    3
    Views:
    2,552
    mlimber
    Jan 24, 2006
  5. Emilio Mayorga
    Replies:
    6
    Views:
    340
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page