# Determine if two edges of a graph cross? [closed]

Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great.

To be clear, here's an example:

The algorithm would ideally return that the edge shared by 7 and 8 crosses with that between 5 and 11. Similarly for 11 and 10, 8 and 9.

## closed as unclear what you're asking by D.W.♦, David Richerby, FrankW, GillesApr 4 '14 at 12:30

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• So do you actually want a planarity test? – Juho Apr 2 '14 at 17:20
• @gjdanis Please explain what you mean by "two edges of a graph cross". Explain clearly that is the input to your problem and what is the required output. – Yuval Filmus Apr 2 '14 at 17:34
• @gjdanis So you are given an embedding of a graph into the plane, and you want to find which edges cross. This is a standard problem in computational geometry: given a list of segments, find which of them intersects. In your case, may of the segments share endpoints, which might make for a more efficient solution, though in principle the degree of each vertex could be 1. – Yuval Filmus Apr 2 '14 at 18:23
• @gjdanis The intersections are not a property of the graph itself. They depend on how the graph is drawn (what Yuval calls "embedding" above). In your example above, if you swap the positions of 5 and 7 and move 10 down far enough, there won't be any intersections left. – FrankW Apr 2 '14 at 19:04
• You still haven't clarified what your input is. Is it a graph (i.e. a set of vertices, like in your last comment here), which may or may not have crossing edges depending on how it is drawn, and if so how would you determine which edges cross? Or is it a figure drawn in a place, consisting of a finite number of segments, such that you know the coordinates of the endpoints? These are completely different problems. – Gilles Apr 4 '14 at 12:30

• I suggest you pick up any textbook on computational geometry. The slope of a line is a concept from analytic geometry, a subject which used to be covered in school. The slope is the "angle" of the line. One way to represent slope is as follows: if the line is $y = mx + b$ then the slope is $m$, and vertical lines $x = b$ have infinite slope. – Yuval Filmus Apr 2 '14 at 18:59