Abstract FR:

Les travaux présentés dans cette thèse concernent les spécifications de dessins de graphe. On introduit la notion de carte partielle dont deux cas extrêmes sont le graphe (sans indication de dessin) et la carte (combinatoire) qui spécifie complètement le dessin (à déformation près) d'un graphe connexe. Des problèmes de réalisabilité de dessin sans croisement d'arêtes, sur le plan, sur des surfaces plus complexes, sont étudiés des points de vue logique et combinatoire au moyen de la structure de carte partielle. Dans la formulation de ceux-ci intervient le problème de l'ordonnancement cyclique. On obtient des caractérisations par configurations exclues de relations cycliquement consistantes, de certaines classes de cartes partielles et des cartes dessinables sur une surface donnée. Ces caractérisations sont exprimables dans la logique du second ordre monadique.