Minimize crossing edges in undirected graph
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:
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