Shiro

I have an undirected graph with N vertices. Each vertex can be on more than one edge. So when I draw this graph on my 2D screen, it can happen that edges will be crossing each other.

It is impossible to avoid crossing edges, but I guess there is some algorithm which is able to minimize the number of crossing edges. Can anyone help me?

Perhaps an "easier" question is: how can I determine whether two edges will be crossing? In graphs coordinates are not used, so there must be a different way than geometric to determine this.

For your information, the graph is implemented as a table:

struct graph
{
int nr_of_vertices;
bool adjacency_table [MAX_VERTICES][MAX_VERTICES];
}

So assume a graph has 4 vertices and the following relations exist (1,2), (1,4) and (2,3). Then the table would look like this:

1 2 3 4
1 T T F T
2 T T T F
3 F T T F
4 T F F T