Sujet : Structurations hiérarchiques des graphes fondées sur des informations attachées à leurs éléments

Responsable : Bruno Courcelle
Téléphone : 05 40 00 60 86
e-mail : courcell@labri.fr
Site Web : http://www.labri.fr/~courcell/ActSci.html
Equipe : LAAA

Présentation du sujet :

La structuration arborescente des graphes est très utile pour la construction d’algorithmes polynomiaux pour les graphes et pour l'obtention de propriétés de décidabilité logique. Mais elle est très contraignante dans la mesure où beaucoup de graphes « naturels » , issus de problèmes concrets ont une structure sous-jacente de réseau, disons de graphe planaire (réseau de routes ou de distribution d’électricité).
Quitte à sacrifier certains résultats de décidabilité logique et d'efficacité algorithmique nécessitant une structuration arbrorescente, une structuration hiérarchique à niveaux multiples et basée sur des graphes planaires pourrait être très utile, en particulier pour obtenir des représentations compactes de graphes, ou bien des représentations enrichies d’informations facilitant les requêtes.
Ces nouvelles structurations ont des applications potentielles en algorithmique des graphes et pour les SIG (Systèmes d'Information Géographique).
L’idée serait dans ce cadre de structurer les graphes, non pas de façon « aveugle » en fonction de propriétés combinatoires, mais en fonction d’une sémantique associée de façon pertinente. Ainsi une information géographique pourrait être structurée hiérarchiquement en différents niveaux : bassins hydrologiques, régions, départements, "pays", communes etc… Les villes pourraient être représentées à un certain niveau comme des sommets d'un graphe, mais à un autre niveau comme des réseaux de rues principales.
Le cadre classique des graphes est inadapté à ces hiérarchies. L’objectif est d’en bâtir un qui soit bien adapté.
L'étape suivante consistera à relier des informations classiques sur les graphes (sommets, incidences) et des informations hiérarchiques de type nouveau, à des données diverses et hétérogènes, stockées dans une base. Plusieurs structurations du graphe sous-jacent pourraient être générées en fonction de besoins différents.
Le sujet consiste à étudier les aspects fondamentaux, à proposer des structures de données adaptées, conduisant à des représentations concises.


Mot-clés : Graphes, structuration des graphes, planarité, bases de données, système d'information géographique

Références :
Articles fournis sur demande par B. Courcelle.

Mise à jour :  Février 2004.