Determine if two edges of a graph cross?
If you don't care about time complexity, the following algorithm would do. Go over all pairs of edges. For each pair, we have to find whether the two segments intersect. There are two cases: the two segments have the same slope, or they don't have the same slope.

If they have the same slope, then they could be two segments on the same line, or they could belong to different lines. In the second case, they don't intersect. In the first case, this is a one-dimensional problem which is easy to solve (you can reduce it to checking whether two intervals on the real line intersect).

If the two segments have different slope, then the corresponding lines intersect at a unique point. It remains to find whether this point also belongs to both segments.



There are probably more efficient solutions out there, but this shows how to solve your problem in a naive way.