je cherche deseperement un algo de planarisation de graphes qui n'enleve pas de sommet ( ie , si il n'est pas planaire , il l'arrange le plus possible mais il n'enleve pas d'aretes ni de sommet )
cet algo ne doit que "reorganiser " le graphes
et je n'arrive pas a trouver ca sur le net

c impossible ca, ou alors tu pose mal ta question.
un graphe est planaire ou pas, pout le planeriser si il l'est pas il faut foircement le modifier.
 
ne pas confondre avec un graphe dessiné de facon non planaire mais qui peut être dessiné de facon planaire (dans tt les cas il est planaire, du moment qu'il existe une solution pour le dessiner sans aretes qui se croisent.)

pardon, je me suis mal exprimé.
vopila ce qu'il me faut :
j'ai un graphe quelconque : soit il est planaire et je veux le tracer de maniere  a ce qu'il n'y ai pas d'intersection d'aretes, soit il ne l'est pas et je dois minimiser le nombre de croisement.
parce que je trouve des docs qui parlent de ces algos , maispas les algo en eu meme, ni les structures de données utilisées.

pareil !

tgenre kartoo ??

Recherche sur google, tout simplement: graph planarization algorithm
 
http://www.mpi-sb.mpg.de/%7Emutzel [...] I-95-1-011
http://www.mpi-sb.mpg.de/~mutzel/d [...] w3eng.html
 
J'ai pas tout lu il n'y a peut-être pas tout, mais en persévérant tu devrais finir par trouver ce que tu cherches.

mr_mat

 
ah okay.
dsl je ne connais pas de tel algo, pourtant j'ai eut des cours de graphe (iut informatique), ce genre de truc se fait au feeling.
mais sur le net ca se trouve certainement.

apres plusierus heures de recherche , changement de voie :  
je ne veux plus rendre un graphe planaire , mais seulement le dessiner correctement, et pour ca , j'ai quelques algos ( malheureusement , ca ne se fait pas au feeling ce genre de truc , vu que ca doit etre hyper optimisé ).
pour info , je pars sur les Force directed graph drawing method et sur les hierarchical drawing method .
la premiere est relativement simple , la 2e a 4 étapes , toutes NP-complet mais avec des heuristiques , j'espere arriver a un resultat concluant .