2

My question is similar to this question. I am using python-igraph library to create undirected graph. What I want to achieve is to untangle as much as possible such that minimum number of crossings of edges is achieved. Then I want convert this clean layout to a 2D plane where I can read the the coordinates of each vertex and no vertex is overlapping any other vertex.

For my current graph I have generated the layout based on the Fruchterman-Reingold force-directed algorithm (as shown in the image).

Can anyone give me some hints how can I achieve that? or this cannot be solved in polynomial time because to find the best placement of vertices with minimum of number of crossing is a NP-Hard problem.

enter image description here

frasheed
  • 75
  • 8
  • 1
    Regarding the node overlap, AFAIK, there is no notion of node dimensions (w.r.t. to the canvas) in the layout routines of `igraph` (or any of the competing libraries such as `networkx`), i.e. they are represented as points, not as circles with a non-zero area. Hence there is no collision detection. So any solution solving that problem would require a substantial amount of work (basically write a simple physics engine that computes the spring forces at any point during the simulated annealing + force due to node collisions, the latter potentially only at "late" stages of the simulation). – Paul Brodersen Feb 04 '19 at 14:33

0 Answers0