0
$\begingroup$

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:

enter image description here

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.

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, FrankW, Gilles Apr 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.

  • 2
    $\begingroup$ So do you actually want a planarity test? $\endgroup$ – Juho Apr 2 '14 at 17:20
  • 3
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Apr 2 '14 at 17:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Apr 2 '14 at 18:23
  • 6
    $\begingroup$ @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. $\endgroup$ – FrankW Apr 2 '14 at 19:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Gilles Apr 4 '14 at 12:30
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 2 '14 at 18:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.