I assume you have the (X, Y) coordinates of each point in your graph.
Determining if two line segments intersect is a solved problem - see How do you detect where two line segments intersect?
All (as if!) you need do is make a list of your line segments, then for each segment determine if it intersects with any segment further down the list (if you've already determined that segment 1 does not intersect segment 3, there's not point in testing if segment 3 intersects segment 1)
If you have thousands of points this is going to be an expensive and slow process unless you put some thought into weeding out line segments that couldn't possibly intersect.
