Cette these traite de l'algorithmique des cartes planaires (graphes dessines dans le plan sans intersection d'aretes) et propose des procedures efficaces pour le codage, la generation aleatoire, et le dessin de plusieurs familles importantes: 3-connexes, triangulations, quadrangulations... En particulier, on decrit le premier algorithme optimal de codage des incidences faces-aretes-sommets des maillages polygonaux de topologie spherique, qui atteint la borne inferieure de 2bits par arete. En partant d'un generateur de cartes 3-connexes, on developpe un nouveau generateur aleatoire uniforme de graphes planaires dont la complexite est la meilleure connue actuellement: quadratique (en esperance) en taille exacte et lineaire (en esperance) en taille approchee. Enfin, on donne plusieurs algorithmes de dessin en lignes droites (aretes representees par des segments) de cartes planaires sur la grille. Les procedures de dessin sont a la fois tres simples a decrire et donnent les meilleures performance (en probabilite) pour le dessin de deux familles de cartes: les triangulations du carre sans 3-cycle rempli —dite irreductibles— et les quadrangulations. Pour developper les algorithmes presentes dans la these, on exploite plusieurs structures combinatoires sur les cartes (orientations specifiques, partitions en arbres couvrants...) ainsi que de nouvelles constructions bijectives.
| Identifer | oai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00002931 |
| Date | 11 June 2007 |
| Creators | Eric, Fusy |
| Publisher | Ecole Polytechnique X |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0019 seconds