arima

Volume 1 - 2002

Fiche article :

bouclier
spacer

 

Algorithme de Calcul du degré de retournement d'un graphe planaire topologique

An algorithm for computing the reversal degree of planar topological graphs

Jean-Pierre Nzali, Koumpo Tanékou Porguy, Hippolyte Tapamo

Département d'Informatique
Faculté des Sciences
B.P. 812 Yaoundé Cameroun
jpnzali@uycdc.uninet.cm

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.

Notes biographiques

Jean-Pierre Nzali est chargé de cours au département d'informatique, Faculté des Sciences, Université de Yaoundé I. Il a déjà publié plusieurs articles sur le degré de retournement d'un graphe.

Koumpo Tanékou Porguy vient d'obtenir son DEA au département d'informatique, Faculté des Sciences, Université de Yaoundé I.

Hippolyte Tapamo est assistant au département d'informatique, Faculté des Sciences, Université de Yaoundé I.

spacer
spacer
 présentation
    description

 accès aux articles
    online access

 nouvelles parutions
    recent articles

 comité de rédaction
    editorial board

 abonnements
    subscriptions

 soumission
    submission

 instructions auteurs
    author information

 contact

spacer

A R I M A  arima-office@inria.fr

  haut de page