Plongements topologiques de graphessur les complexes simpliciaux
Thomas Magnard · HAL (Le Centre pour la Communication Scientifique Directe) · 2021
L'étude des plongements topologiques de graphes, c'est-à-dire des manières de dessiner sans croisement un graphe dans un espace topologique, constitue un domaine classique à l'interface des mathématiques et de l'informatique dans les communautés de topologie, théorie topologique des graphes, topologie algorithmique et dessin de graphes. Il est naturel de s’intéresser à la plongeabilité des graphes sur des espaces topologiques généraux tels que le plan, les surfaces ou des espaces de plus grande dimension. Or, comme tous les graphes sont plongeables dans un espace tridimensionnel, les espaces topologiques pour lesquels la question est non triviale sont de dimension au plus deux. Il est ainsi logique de considérer comme classe d'espaces la classe des complexes simpliciaux de dimension au plus deux, les espaces obtenus en recollant des sommets, des arêtes et des triangles. En particulier, ces espaces topologiques contiennent les surfaces, et le problème est déjà NP-difficile même en se restreignant aux surfaces. Cette thèse présente deux algorithmes décidant le problème de la plongeabilité d'un graphe sur un 2-complexe. Les deux algorithmes fonctionnent en temps polynomial en la taille du graphe lorsque le complexe est fixé, mais seul le second est "fixed parameter tractable" quand paramétré par la taille du 2-complexe donné en entrée. Le premier algorithme est basé sur des arguments d'ordre topologique. Sa stratégie consiste à réduire le problème de la plongeabilité d'un graphe sur un 2-complexe à un problème d'extension de plongement d'un graphe sur une surface pour lequel il existait déjà un algorithme dû à B.Mohar. De plus, dans le même temps, cette approche montre aussi que le problème est dans NP. Le second algorithme est basé sur des arguments d'algorithmique des graphes. Il commence par retirer itérativement du graphe des sommets inutiles jusqu'à ce que le graphe ait une largeur de branche bornée. Ensuite, il utilise une stratégie de programmation dynamique qui décide si un graphe de largeur de branche bornée est plongeable sur un 2-complexe