Sujet : Dessin et mineur de graphe

Responsable : Cyril Gavoille
Contact : gavoille@labri.fr
Équipe : Combinatoire et Algorithmique
Thème : Graphes et Optimisation
Type : stage Master Informatique
Durée : 5 mois en 2020
Lieu : LaBRI
Financement : acquis le 18/12/2019 (LaBRI)
Mot-clés : graphe, dessin de graphe, mineur, largeur arborescente

Présentation du sujet :

Il s'agit d'étudier la relation entre l'aire nécessaire pour dessiner un graphe $H$ et la largeur arborescente des graphes, pas forcément planaire, sans $H$ comme mineur. On pourra dans un premier temps considérer le cas des graphes planaires sans mineur $H$. Il a été démontré récemment dans [DG20] que tout graphe planaire $G$ sans mineur $H$ possédant un dessin avec des arêtes brisées sur une grille $p\times q$ possède une largeur aborescente $O(p\sqrt{q}\,)$. Ce résultat est basé sur l'algorithme de dessin de [Biedl14a]. Cependant il n'est pas connu si cette borne sur la largeur arborescente peut être atteinte. Il s'agira de déterminer si tel est le cas, ou si cette borne supérieure peut être diminuée, par exemple d'un facteur $\sqrt{p}$. D'autres pistes qui pourront être envisagées est de déterminer cette largeur arborescente dans le cas où $H$ est un graphe $k$-planaire-extérieur.

Ce sujet se rattache à un domaine de recherche novateur, ayant de nombreuses extensions (soit en terme de famille de graphes, soit en terme de type dessins) et peut faire l'objet, selon la motivation et le travail du candidat, d'une poursuite en thèse.

Références :

[login: gavoille, pwd: bib0]

  • [DG20] Youssou Dieng and Cyril Gavoille. On the Treewidth of Planar Minor Free Graphs. 2020.

  • [Biedl14a] Therese C. Biedl. Height-preserving transformations of planar graph drawings. In 22nd International Symposium on Graph Drawing (GD), volume 8871 of Lecture Notes in Computer Science, pages 380-391. Springer, September 2014.