J'ai dessiné un small planar graph avec Graphviz mais dans un endroit il y a une intersection de deux arêtes. Je lis sur SO que tous les graphes planaires ne peuvent pas être dessinés sans intersections car c'est un problème NP-difficile. J'ai aussi lu qu'il n'y a même pas d'algorithmes complexes implémentés dans Graphviz qui le font. Mais cette intersection est aussi facile à réparer que possible, il y a probablement moyen de s'en débarrasser.Dessin de petits graphiques planaires avec Graphviz
Voici les options que j'utilise:
overlap = false;
splines = curved;
nodesep = 0.5;
Et voici le graphique: 
Alors, est-il un moyen de fixation dont une intersection (25-38 avec 7-18) sans changer l'ordre des bords comme je l'ai fait here? N'y at-il pas au moins O(n^2) algorithme qui permuterait deux sommets et vérifierait si l'intersection a disparu?
Il y a 'O (N)' algorithmes [[1] (https://archive.org/details/PlanarityTestingByPathAddition) [2] (https: // dl.acm.org/citation.cfm?id=321852)] pour tester la planarité et ils le font en créant un embedding planaire. Il est toujours possible de créer une incrustation d'un graphe planaire sans croisement de bord (puisque c'est la définition d'un graphe planaire) et ce n'est pas un problème NP-difficile et s'il y a des réponses indiquant qu'ils sont faux. Cela dit, je n'ai jamais utilisé GraphVis donc je ne peux pas vous aider à le résoudre dans ce programme. – MT0
@ MT0 Je sais qu'il y a des vérifications graphiques rapides. Je voulais dire que dessiner des graphes planaires est NPH. Mais j'avais tort. J'ai vérifié et j'ai lu [lire] (https://stackoverflow.com/a/2348551/2377652) que dessiner un graphique avec le moins de fronts qui se croisent est NPH. Ma faute. – user1
Dessiner un graphe non planaire avec un minimum de croisements est difficile - dessiner un graphe planaire sans croisement de bord est un problème qui a été résolu en temps linéaire ('O (N)') - voir le premier lien dans mon précédent commentaire pour une méthode parmi beaucoup d'autres. – MT0