2

Lets imagine I have points in a 2D plane that I want to connect in a directionless graph. However, I don't want these connections to overlap. The only data I'm given is where a connection exists, and what direction is goes. For example, one of my (very simple) data sets might look like this

1 > 2

2 > 3

4 > 3, 5

5 > 3

And thus, a good example of what I would want would look like this:

This image does not have any overlapping points of connections, and would be one of the many solutions. The graphing portion of the algorithm is not a problem to me. I really just want an algorithm that could return the coordinates of the various points to me, and then I can take over from there.

On the other hand, this is what I do not want:

I'm not necessarily looking for actual code, but merely a nudge in the right direction, or perhaps an algorithm that I can adapt to my specific data. Pseudo code would be fine if necessary to answer the question.

EDIT:

Now, of course I could just check if the line segments intersect in a example this small, but normal data sets for this algorithm will be much larger. It would not be efficient to calculate each and every point placement manually, and would most likely not result in the most 'optimized' solution.

  • I guess you are heavily underestimating the complexity of the task. Graph drawing is a whole area of scientific research. – Doc Brown Aug 6 '16 at 8:11
  • @DocBrown Oh I just tried to make my problem as easy to understand as possible with as simple language as possible. – Nick Pandolfi Aug 6 '16 at 18:57
1

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.

| improve this answer | |
  • There could be up to 100,000 points at a given time, so I was looking for a way in which one would not have to do it manually like that. If I had to check all the connections then that would be O(n^2) or even longer with additional constraints. I wanted something more 'automatic' in a sense. – Nick Pandolfi Aug 6 '16 at 1:30
  • 1
    I had a feeling that was the case. Check the link in my answer - they talk about filtering out a lot of segments that couldn't possibly intersect (e.g., both points of segment 1 are above both points of segment 2) – Dan Pichelman Aug 7 '16 at 0:00
  • Thats a good point. Alone this might not be the best solution, however I was thinking that this method paired with a force directed graphing system would work nice. The line intersection detections would help drastically by untangling the mess. See this: bl.ocks.org/mbostock/4062045 – Nick Pandolfi Aug 7 '16 at 3:16
1

(Disclaimer: I don't know enough graph theory to determine whether the following information is correct.)


If you only have the graph, i.e. labels for vertices, and edges defined between two vertices, i.e. you do not have the coordinates:

To check whether a given graph is planar, the Wikipedia article on Planar Graph lists many algorithms for doing so.

The same article also gives examples of graphs which are not planar. If you are given such a graph, it is futile to try to find a planar embedding for it.


If you want to use a software to generate coordinates for such a graph:

Take a look at the list of graph layout software on these Wikipedia articles:

Note that these software do not guarantee non-crossing, even for graphs that are planar. This is explained in the following Stack Overflow post:


As far as an ordinary software programmer is concerned (i.e. not an expert in graph theory and algorithms), this problem is complicated enough that an ordinary person should not attempt to solve it alone.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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