Fiche article :

RÉSUMÉ. Le degré de retournement est une caractéristique des graphes planaires topologiques. Dans cet article nous proposons un algorithme amélioré pour calculer le degré de retournement d'un graphe planaire topologique. Cet algorithme explore les différents cas possibles suivant une méthode descendante. Son implémentation sur machine a donné lieu à des tests sur des cas pratiques, ceci en des temps de calcul tout à fait raisonnables, sur des graphes dont l'un comporte plus d'une cinquantaine de sommets intérieurs de degré impair.

ABSTRACT. One characteristic of planar topological graphs is the reversal degree. In this paper, we propose an improve algorithm for calculating the reversal degree of a planar topological graphs. This algorithm explores various possible cases following the descending method. Practical tests carried out on machine, using graphs with more than fifty internal vertices of odd degree, have been realized within reasonable computing time.

MOTS-CLÉS : graphe planaire topologique, degré de retournement, algorithme, carte, SIG.

KEYWORDS: planar topological graph, reversal degree, algorithm, map, GIS.