Cette thèse se concentre sur la problématique suivante : comment assister un utilisateur novice pour l'aider à obtenir un dessin de son graphe qui soit adapté à ses besoins ? En effet, les méthodes de dessins actuelles, très nombreuses, nécessitent une grande expertise pour obtenir un dessin de bonne qualité. Or, par manque d'expertise, les utilisateurs novices ne peuvent pour l'instant pas produire des dessins d'une telle qualité à partir de leurs données. La solution proposée consiste à mettre en place un système interactif proposant à l'utilisateur différents dessins pour un même graphe afin qu'il obtienne un résultat qui réponde correctement à ses besoins. Ce système se base sur un algorithme de force modifié utilisé par un système d'algorithme génétique hautement modulable. L'objectif de la modification apportée à l'algorithme de dessin étant de pouvoir générer plusieurs dessins intéressants pour un même graphe. / The main objective of this thesis is to deal with assisting a novice user in drawinga graph which conforms to his/her needs. Currently, a lot of different methods for graph drawing exist, but they need an high level of expertise to be efficiently used. However, novice users don't have this kind of expertise, and thus they usually use the most common drawing methods. We design a solution to deal with this problem using an interactive system which generate several different drawings for a graph and then let the user choose which best conform to his/her constraints. This system is based on a modified force-directed algorithm controlled by a highly parameterisable genetic algorithm. The aim of the modification applied to the force-directed algorithm is to generate several different and interesting drawings of the same graph, by setting the parameters for each vertex (instead of global graph values).

<p dir="ltr">This dissertation introduces a novel graph embedding paradigm, leveraging a force-directed scheme for graph embedding. In the field of graph embedding, an "embedding" refers to the process of transforming elements of a graph such as nodes, or edges, or potentially other structural information of the graph into a low-dimensional space, typically a vector space, while preserving the graph's structural properties as much as possible. The dimensions of the space are supposed to be much smaller than the elements of the graph that are to be embedded. This transformation results in a set of vectors, with each vector representing a node (or edge) in the graph. The goal is to capture the essence of the graph's topology, node connectivity, and other relevant features in a way that facilitates easier processing by machine learning algorithms, which often perform better with input data in a continuous vector space.</p><p dir="ltr">The main premise of kinematics-based force-directed graph embedding is that the nodes are considered as massive mobile objects that can be moved around in the embedding space under force. In this PhD thesis, we devised a general theoretical framework for the proposed graph embedding paradigm and provided the mathematical proof of convergence given the required constraints. From this point on, the objective was to explore force functions and parameters and methods of applying them in terms of their efficacy regarding graph embedding applications. We found some force functions that outperformed the state-of-the-art methods.</p><p dir="ltr">The author of this manuscript believes that the proposed paradigm will open a new chapter, specifically in the field of graph embedding and generally in the field of embedding.</p>