Thèse Theorie des Graphes Géométrique H/F - 33

Établissement : Université de Bordeaux
École doctorale : Mathématiques et Informatique
Laboratoire de recherche : LaBRI - Laboratoire Bordelais de Recherche en Informatique
Direction de la thèse : Cyril GAVOILLE ORCID 0000000336718607
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-04T23:59:59

Les graphes interagissent étroitement avec la géométrie par le biais des dessins de graphes, un domaine vaste et important de la géométrie algorithmique. Ici, nous considérons le graphe complet dessiné sur un ensemble de points en position générale avec des arêtes en ligne droite, également appelé graphe géométrique. Il est connu que les arêtes en ligne droite, bien que réduisant la complexité de la représentation, sont sous-optimales par rapport à certains paramètres combinatoires, comme le nombre de croisements du dessin.

Les célèbres dessins de Hill montrent qu'il existe des dessins du graphe complet avec 3/8 binom(n,4) croisements d'arêtes ; en revanche, le nombre de croisements d'arêtes dans tout dessin en ligne droite du graphe complet est d'au moins 0.37 binom(n,4). Un phénomène similaire se produit pour l'épaisseur géométrique comparée à l'épaisseur topologique. L'épaisseur d'un dessin est le nombre minimal de graphes plans en lesquels un dessin peut être partitionné.

Notre objectif général est de comparer davantage les dessins en ligne droite et les dessins où les arêtes sont représentées par des courbes arbitraires, en termes de propriétés combinatoires. De manière similaire à l'épaisseur, notre attention se porte sur l'intégration de graphes plans dans des dessins de manière planaire, avec des questions allant de l'universalité à l'empilement de graphes.

Etudiez les versions géométriques de problèmes de théorie des graphes

Recherche en collaboration au sein de l'équipe 'Graphe et Optimisation' du LaBRI, et plus généralement des équipes du département Combinatoire et Algorithmique du LaBRI.