Algorithm to design a graphic of a set of connections between nodes

Question

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.

Answer 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.

Answer 2

(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:

• https://en.wikipedia.org/wiki/DOT_(graph_description_language)
• https://en.wikipedia.org/wiki/Graphviz

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

• https://stackoverflow.com/questions/2347748/planar-graph-layouts

---

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.