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