(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:
- http://stackoverflow.com/questions/2347748/planar-graph-layoutshttps://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.
