Minimiser les bords croisés dans un graphique

Question

J'utilise l'utilisation de NetworkX (un package de dessin de graphique Python) http://networkx.lanl.gov/index.htmlLe_a> pour un de mon projet.Bien que NetworkX soit assez cool, le type de fonction d'affichage est nul en raison du nombre de bords croisés.Existe-t-il un moyen de minimiser les arêtes croisées dans un graphique?Je veux dire un algorithme qui peut trier les nœuds de manière à ce que les bords croisés soient minimisés?

Answer 1

Determining a planar graph layout which minimizes the number of crossings is NP-Hard. See the wiki page on Crossing Number.

You could try some heuristics, force based layout are quite popular I believe (graphviz uses them, if I recollect correctly).

You could also try some approximation algorithms, you should find references on the wiki page I linked.

Hope that helps.