Théorie métrique et structurelle des graphes // metric and structural graph theory

Topic description

Le sujet du projet de recherche se situe à l'intersection de la théorie structurelle des graphes et de la géométrie. De nombreuses classes de graphes bien étudiées, comme les graphes planaires (ou plus généralement excluant un mineur) se comportent bien de manière métrique. Par exemple, les graphes excluant un mineur sont de dimension asymptotique au plus 2 et les graphes de largeur arborescente bornée sont de dimension asymptotique au plus 1. Le but de la thèse sera de comprendre, si à l'inverse, les classes qui se comportent bien de manière métrique peuvent être obtenues à partir de classes comme les graphes planaires (ou excluant un mineur) par des opérations préservant la métrique (de manière exacte ou approximative). Un partie importante du projet de recherche consistera à comprendre la structure des graphes excluant un sous-graphe quasi-isométrique donné (c'est-à-dire un sous-graphe dont la métrique est proche de celle de son image dans le graphe original, ou excluant un 'fat-minor', qui est une version métrique de la notion classique de mineur.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The topic of the research project lies at the intersection of structural graph theory and geometry. A number of well-studied graph classes, such as planar graphs (or more generally avoiding a minor) behave very well from a metric point of view. For instance, graphs excluding a mi- nor have asymptotic dimension at most 2 and graphs of bounded treewidth have asymptotic dimension at most 1. The goal of the thesis is to understand whether, conversely, graph classes that are simple from a metric point of view can be obtained from classes such as planar graphs (or graphs excluding some minor) using metric-preserving operations. An important part of the research project will be to understand the structure of graphs excluding some fixed quasi-isometric subgraph (that is, a subgraph whose metric is not very different from that of its image in the original graph), or a fixed 'fat-minor', which is a metric variant of classical graph minors.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/

Funding category

Funding further details

Concours allocations