Une professeure de l’Université d’Ottawa résout un problème vieux de 30 ans en théorie des graphes planaires

Faculté de génie
Science informatique et génie électrique
Recherche et innovation
Vida Dujmovic
Avec ses collègues, la chercheuse Vida Dujmović de la Faculté de génie vient de résoudre un problème de longue date lié aux graphes planaires, réalisant ainsi d’importantes percées dans ce domaine.

Dans le monde des mathématiques et de l’informatique, les graphes servent à modéliser des systèmes complexes ayant des applications dans une multitude de disciplines.  

Un graphe est composé d’un ensemble de nœuds (aussi appelés sommets) reliés par paires par des arêtes. Les nœuds du graphe représentent des entités individuelles, tandis que les arêtes représentent les liens entre elles. 

Graphique planaire
Graphique planaire

On peut se servir de graphes pour représenter un large éventail de situations réelles : réseaux routiers, réseaux informatiques et de communication, réseaux sociaux, représentations moléculaires, réseaux sous-jacents aux marchés financiers, etc. En modélisant ces situations à l’aide de graphes, les chercheuses et chercheurs peuvent analyser divers phénomènes tels que la propagation de l’information (et de la mésinformation), la dynamique des communautés en ligne ou la migration des populations. 

 

Malgré leur apparente simplicité, les graphes ont une structure riche et complexe qui intrigue la communauté de recherche et celle des mathématiques depuis déjà longtemps. Si certaines familles de graphes sont bien comprises, d’autres sont autrement plus compliquées et moins bien, voire très mal comprises, comme c’est le cas des graphes planaires.  

Or, la professeure Vida Dujmović (Faculté de génie) a réussi à résoudre certains problèmes de vieille date en posant un théorème révolutionnaire qui répond à la question suivante : quelle est la structure générale des graphes planaires? L’existence de problèmes persistants comme ceux-là laisse souvent supposer qu’un élément fondamental de la théorie échappe à notre compréhension. Et c’est justement en cherchant à mieux comprendre les graphes planaires que la chercheuse, épaulée par ses proches collaborateurs à l’étranger Gwenaël Joret (Belgique), Piotr Micek (Pologne), Pat Morin (Canada), Torsten Ueckerdt (Allemagne) et David R. Wood (Australie), en est venue à poser le théorème de la structure de produits des graphes planaires.  

Grâce à ce théorème, elle a démontré que les graphes planaires peuvent être exprimés comme un produit de deux graphes simples et bien compris, à savoir une chaîne et un graphe de largeur arborescente 8.  

Vida Dujmovic et ses collègues internationaux
Vida Dujmovic et ses collègues internationaux

Ce théorème a permis à l’équipe de résoudre plusieurs problèmes tenaces, notamment une conjecture sur l’étiquetage d’adjacence datant de 1988, une conjecture en lien avec la disposition des files d’attente de 1992 et une autre sur la coloration non répétitive de 2002. 

« Ça fait plus de 15 ans que le problème de la disposition des files d’attente m’inspire. J’y revenais sans cesse, munie de nouveaux outils, pour m’y attaquer sous différents angles, mais cette ultime conjecture continuait de me résister malgré les progrès réalisés au fil des années », déclare la chercheuse. 

Finalement, c’est la découverte de la structure de produits qui l’a amenée à trouver la clé.  

« Comme ça arrive parfois en sciences et en génie, les outils découverts dans la recherche de solution se sont avérés plus importants que le problème lui-même », explique-t-elle. 

Son théorème de la structure de produits semble faire partie de ces outils, vu le grand nombre d’éminents problèmes qu’il permet de solutionner, non seulement pour la chercheuse et ses collègues, mais pour toute la communauté de recherche. 

La Faculté de génie félicite la professeure Dujmović et son équipe pour leurs extraordinaires contributions à la théorie des graphes. Les personnes et les organisations qui souhaiteraient collaborer à ces travaux peuvent contacter directement Vida Dujmović