title: Minimize crossings in a radial graph (networkx, graphviz)
body: <p>I have a complicated graph that I build using the python networkx library and I am trying to draw it in an understandable way. My data is structured in a way that I always have a central node, then a set of nodes that are at distance 1 from the center, and then another set of nodes which are at distance 2 from the center. By "distance" I mean the minimum number of edges before reaching the central node. Because of this structure, I would like to draw the graph in a radial fashion, where the distance-1 nodes lay on a circumference of a fixed radius from the center, let's say <code>r=1</code>, and the distance-2 nodes on a circumference of <code>r=2</code>.
  Something like this:
  <a href="https://i.stack.imgur.com/yqysB.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/yqysB.png" alt="enter image description here"></a>
  I tried different approaches, but the most promising one so far has been to use the <a href="https://networkx.github.io/documentation/stable/reference/generated/networkx.drawing.layout.shell_layout.html" rel="nofollow noreferrer"><code>networkx.drawing.layout.shell_layout</code></a>, that produces the following layout:
  <a href="https://i.stack.imgur.com/pn6CK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pn6CK.png" alt="enter image description here"></a>
  All the nodes are at the right distance from the central one, but the problem is that the position of the nodes on the circumferences is not chosen to minimize the edge crossings. This is clearly stated in the linked page "This algorithm currently only works in two dimensions and does not try to minimize edge crossings". I have looked both in the <a href="https://networkx.github.io/documentation/stable/" rel="nofollow noreferrer">networkx library documentation</a> and in the <a href="http://pygraphviz.github.io/documentation/pygraphviz-1.5/" rel="nofollow noreferrer">pygraphviz one</a>, but I have not found layouts that allow for minimisation of crossings and positioning the nodes on concentric circumferences at the same time. Does anybody know how to do that?</p>
  
  <p>Edit: Here are the edges of the graph shown in figure 2 (it's a directed graph!).</p>
  
  <pre><code>edges = [((3, 446), (3, 439)), ((3, 446), (3, 502)), ((3, 446), (3, 2366)), ((3, 446), (3, 382)), ((3, 446), (3, 3556)), ((3, 446), (4, 1778)), ((3, 446), (3, 1214)), ((3, 446), (3, 445)), ((3, 446), (4, 758)), ((3, 439), (2, 253)), ((3, 439), (3, 446)), ((3, 439), (3, 3482)), ((3, 439), (4, 1763)), ((3, 439), (3, 2359)), ((3, 439), (3, 319)), ((2, 253), (3, 439)), ((2, 127), (3, 502)), ((3, 502), (2, 127)), ((3, 502), (3, 446)), ((3, 502), (3, 4004)), ((3, 502), (3, 508)), ((3, 502), (4, 998)), ((3, 502), (3, 3986)), ((3, 502), (4, 2018)), ((3, 502), (3, 1270)), ((3, 4004), (3, 502)), ((3, 4004), (3, 3556)), ((4, 1270), (4, 758)), ((4, 758), (3, 446)), ((4, 758), (4, 998)), ((4, 758), (4, 502)), ((4, 758), (4, 638)), ((4, 758), (4, 743)), ((4, 758), (4, 1270)), ((3, 508), (3, 502)), ((4, 2300), (3, 382)), ((3, 382), (4, 2300)), ((3, 382), (3, 254)), ((3, 382), (3, 446)), ((3, 1270), (3, 1214)), ((3, 1270), (3, 502)), ((3, 1214), (3, 1270)), ((3, 1214), (3, 446)), ((3, 1214), (3, 1207)), ((3, 1214), (3, 254)), ((3, 3482), (3, 439)), ((3, 3482), (3, 3538)), ((2, 254), (3, 3556)), ((3, 3556), (3, 4004)), ((3, 3556), (2, 254)), ((3, 3556), (4, 1660)), ((3, 3556), (3, 446)), ((4, 1763), (3, 439)), ((4, 1763), (4, 1778)), ((2, 191), (3, 2366)), ((3, 2366), (4, 3190)), ((3, 2366), (3, 2359)), ((3, 2366), (3, 446)), ((3, 2366), (2, 191)), ((4, 3190), (3, 2366)), ((4, 998), (4, 758)), ((4, 998), (3, 502)), ((3, 3986), (3, 502)), ((3, 3986), (3, 3538)), ((3, 2359), (3, 2366)), ((3, 2359), (3, 439)), ((4, 1660), (3, 3556)), ((4, 3698), (4, 1778)), ((4, 1778), (4, 2018)), ((4, 1778), (4, 1780)), ((4, 1778), (4, 1763)), ((4, 1778), (3, 446)), ((4, 1778), (4, 3698)), ((4, 2018), (4, 1778)), ((3, 254), (3, 382)), ((3, 254), (3, 1214)), ((4, 1780), (4, 1778)), ((4, 502), (3, 382)), ((4, 502), (4, 758)), ((4, 638), (4, 758)), ((3, 319), (3, 439)), ((4, 743), (4, 758)), ((4, 743), (3, 439)), ((3, 1207), (3, 439)), ((4, 3320), (3, 445)), ((3, 445), (3, 446)), ((3, 445), (4, 3320)), ((3, 445), (3, 443)), ((3, 443), (3, 3538)), ((3, 3538), (3, 3986)), ((3, 3538), (3, 3482)), ((3, 3538), (3, 446)), ((3, 3538), (3, 443)), ((4, 1777), (4, 1778))]
  </code></pre>