– GRATOS

Nous nous proposons d?étudier des graphes définis par le biais d'outils topologiques de differentes natures. Nous nous interesserons entre autre aux classes de graphes définies par des systemes d?objets géométriques s'intersectant dans le plan ou l'espace, aux hypergraphes ayant des plongements dans Rd (à travers les complexes simpliciaux), et des paramètres tels que celui de Colin de Verdiere. On se propose dans un premier temps d?étudier ces trois problématiques. L?objectif de cette étude sera de mieux cerner ces objets mathematiques afin de developper des outils dans le but de d'étendre certaines de leurs propriétés à des cas plus généraux. ? Par exemple, concernant les graphes définis par des systèmes d'objets géométriques s'intersectant, le cas des graphes définis par des systèmes d'intersection de segments dans le plan est bien connu et nous voudrions passer à l'étude des familles de graphes définis par des models d?intersections d'objets géométriques plus complexes dans des espaces de dimensions supérieures. ? Pour les complexes simpliciaux de Rd, comme ceux-ci généralisent le cas des graphes planaires, on se propose d'étendre à ces objets certaines techniques spécifiques aux graphes planaires. Ceci pourrait aboutir à une élégante généralisation de résultats sur les graphes planaires aux complexes simpliciaux. ? Nous nous intéresserons également à certains paramètres permettant de donner une « mesure » de la complexité des familles de graphes. De tels paramètres existent, le paramètre de Colin de Verdière par exemple. On se propose d?introduire de nouveaux paramètres basés sur certaines propriétés structurelles. Dans un deuxième temps, nous étudierons différents problèmes algorithmiques pour les familles de graphes et d'hypergraphe traités auparavant. Les travaux que nous auront mener au préalable nous permettrons certainement d'obtenir des algorithmes intéressants pour ces classes de graphes. Finalement, nous souhaitons montrer que certaines familles de graphes ou d'hypergraphes admettent des réprésentations définies par modèles d?intersection d?objets géométriques. Ceci généraliserait certains résultats connus du domaine.