Abstract FR:

Cette these presente des algorithmes de generation aleatoire et des resultats d'enumeration pour les plongements de graphes ou cartes. Une premiere partie est consacree aux cartes planaires. La conjugaison d'arbres y est introduite et permet d'expliquer et de generaliser des resultats d'enumeration de w. T. Tutte et d'a. Hurwitz. Dans le meme temps, des algorithmes de generation aleatoire uniforme sont obtenus pour des familles elementaires de cartes. Une methode d'extraction/rejet permet alors d'etendre de maniere significative leur domaine d'application et leur efficacite. En particulier sont traites les cas jusqu'ici inaccessibles des polyedres convexes et des graphes planaires maximaux. L'etude de la complexite de ces algorithmes fait appel a des methodes analytiques. Comme premier exemple significatif d'application experimentale des generateurs, une conjecture sur le diametre des cartes planaires aleatoires est presentee. Dans une seconde partie les plongements dans les surfaces de genres superieurs sont abordes. Une bijection permet de donner un codage de ces cartes a l'aide de cartes a une face. Le reste de la these est consacre a obtenir des resultats d'enumeration, qui unifient les resultats connus pour cette famille.