Find random locations of a network that make no overlap between the lines connect them

I am not sure if this is possible in Matlab; I have a network consists of hundreds of nodes P(X,Y) with hundreds of branch (lines). The connectivity matrix [C] is known and it describes the connection between the nodes (from-to). I want to draw this network in an x-y plane with random locations for the nodes. However, I want to avoid choosing xy-locations that lead to an overlap between the branches except if there is no way to avoid it. For my problem, it does not matter for the lines to be plotted; I want to find only the xy-locations (and plot these points) that make no-overlapping except when it's unavoidable. Any idea to do so? Is it possible in Matlab? Thanks in advance

Answer 1

[Walter Roberson]

Apparently it is a very hard problem.

https://cs.brown.edu/~rt/gdhandbook/chapters/crossings.pdf

[John BG]

humbly concurrence

to solve this in a general sense you probably would need to write a thesis.

If you write and pass a thesis to solve this in a general sense and put it in your CV, send it to Cheltenham, they may give you a job.

Found some links that may be useful

http://www.cs.jhu.edu/~misha/Fall07/Papers/Tutte63.pdf

https://en.wikipedia.org/wiki/Graph_automorphism

https://en.wikipedia.org/wiki/Graph_isomorphism

http://www.sciencedirect.com/science/article/pii/0095895672900238

http://uk.mathworks.com/matlabcentral/fileexchange/32726-compute-a-tutte-map-of-a-planar-surface-triangulation

Please keep us posted

[Ismaeel]

Thank you Walter, John... Just wondered if it's possible but apparently it's more than difficult to solve such a problem. Thanks all