# How to untangle a graph to have the fewest number of crossed edges?

So I'm not exactly sure how to ask this questions, so any edits will be appreciated.

I'm looking to see how I can take a graph of V vertices and E directional edges, and untangle it in a 2D planar fashion such that only a relatively low number of edges cross. An efficient algorithm that is a close solution would be better than a slow algorithm that comes to a perfect solution. Grouped edge crossings would also be a feature, if possible. (So that if two options exist, but one option has 'parallel' edge crossings, it would be preferred.)

Ideally, clustering of similarly connected vertices would occur, which would result in grouped parallel edge crossings.

As you can guess from my usage of the word algorithm, I am planning on implementing this in a program. That is the reason that I'm looking for a close solution rather than a perfect one. For an idea of the scope that I'm looking at, I'll have on the order of 2-300 vertices, and possibly several thousand edges, and would rather this algorithm be completed in a reasonable time, rather than going through every possible permutation.

• Keywords for a web search: crossing number, planar embedding, approximation algorithm. – Aryabhata Apr 18 '17 at 0:26