Elegant and efficient way to traverse through edges and resolve intersections

Question

I have an array which represents adjacency matrix of a graph like this.

connections:Array = [0,0,1,1,
                     0,0,1,1,
                     0,0,0,1,
                     0,0,0,0];

Every node of the graph has a 2D point assigned to it which represents its position on a plane. I am trying to write a function which traverses through all the edges and returns false if any of the two edges intersect. Here is my code

function test():boolean
{
    for (i = 0; i < nodes.length ; i++)
    {
        for (j = i ; j < nodes.length ; j ++)
        {
            if (connections[i * nodes.length + j] == 1)
            {
                //we found an edge
                //This is the place where i am stuck I, can't figure out how
                //to take pairs of edges to test them for intersections
            }
        }
    }
}

You can give the answer in any language or even pseudo code.

Note: I don't need any code for intersection algorithm.

Answer 1

While traversing the adjacency matrix, build an edge-centered data structure. The easiest option is a plain list of edges. Then you can iterate all previously visited edges, which will give you a complexity of O(V^2 + E^2), where V is the number of vertices and E the number of edges.

If you have potentially large graphs, you might want to use more efficient data structures, such as a BSP tree that you build on-the-fly. This will get your complexity down to O(V^2 + E log E).