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.