Discussion :

[AP]

Bonjour,
Je souhaiterais dessiner un graphe et pour cela j'aimerais déterminer les coordonnées de chaque noeud du graphe afin que les arcs se croisent le moins possible.
Avez-vous des idées pour réaliser cela?

[pititom51]

Salut,

il y a l'outil dot de graphviz qui fait ca ...

dot - makes ``hierarchical'' or layered drawings of directed graphs. The layout algorithm aims edges in the same direction (top to bottom, or left to right) and then attempts to avoid edge crossings and reduce edge length.

... et il est open source.

[PRomu@ld]

Fait une recherche du coté des graphes planaires.

[AP]

Merci pour vos réponses.
pour Graphviz, j'avais déjà regardé les sources mais elles sont le résultat de plusieurs années de travail et assez dur (voir impossible) à comprendre sans y passer un temps plus que considérable.
Concernant les graphes planaires, c'est une bonne piste mais malheureusement ils ne sont pas forcément planaires.

Si vous avez d'autres idées je suis preneur

[lyxthe]

euh sans trop être sur de ce que je raconte, il s'agit là d'un problème NP-Complet, donc tu ne pourras jamais que trouver une heuristique interessante à mettre en oeuvre, mais à priori c'est compliqué, et long.
Dans Dotti, il y a une option qui te permet de dessiner des graphes dont les aretes se coupent le moins possible, et dès que tu dépasses une soixantaines de points, il faut attendre plus de 5 minutes avant de voir apparaitre quelque chose à l'écran. Enfin j'espere pour toi que je racontes des bêtises, mais si ce n'est pas le cas, je te souhaite bonne chance.