Plongements topologiques de graphessur les complexes simpliciaux

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-complexeThe study of topological embeddings of graphs, that is to say the ways of drawing without crossing a graph in a topological space, constitutes a classic field at the interface of mathematics and computer science in communities of topology, topological graph theory, computational topology and graph drawing. It is natural to be interested in the embeddability of graphs on general topological spaces such as the plane, surfaces or larger spaces. However, as all graphs can be embedded into a three-dimensional space, the topological spaces for which the question is non-trivial are of dimension at most two. It is thus logical to consider the class of simplicial complexes of dimension at most two, the spaces obtained by gluing together vertices, edges and triangles. In particular, these topological spaces include the class of all surfaces and the problem is already NP-hard even if we restrict ourselves to surfaces.This thesis presents two algorithms deciding the problem of the embeddability of a graph on a 2-complex. Both algorithms operate in polynomial time in the size of the graph when the complex is fixed, but only the second is fixed parameter tractable when parameterized by the size of the 2-complex given as input. The first algorithm is based on topological arguments. Its strategy consists in reducing the problem of the embeddability of a graph on a 2-complex to an embedding extension problem of a graph on a surface for which there already existed an algorithm due to B.Mohar. Moreover, at the same time, this approach also shows that the problem is in NP.The second algorithm is based on graph algorithmic arguments. It begins by iteratively removing unnecessary vertices from the graph until the graph has a bounded branch width. Then, it uses a dynamic programming strategy which decides whether a graph of bounded branch width is embeddable on a 2-comple