I'm currently working as a graduate assistant in Université Côte d'Azur and affiliated to the i3S laboratory. My main research interests are graph drawing and graph topology. I also work on the division and root of functional grpahs with respect to the direct product. I did a PhD in computer science in Université Côte d'Azur, under the supervision of Enrico Formenti.
Graphs are widely used data structures, both from a theoretical and practical point of view. Because of their importance, it is necessary to find the best tools for representing them in order to extract the latent information that lies behind the data.
Graph drawing is a lively research area in which a large number of algorithms exist, each focusing on specific properties of the graph or its representation. These include, among others, the minimum angle formed by two edges with a common vertex, the homogeneity of edges length, the number of edge breaks or the number of edge crossings. For some of these parameters, minimizing them is a difficult task. This is particularly true for the crossing minimization problem, which generally turns out to be at least NP-complete.
Several approaches can be explored to tackle this problem, either through generalist algorithms or through more specialised heuristics, each offering a different balance between results and performance. In this thesis, we define a new heuristic, based on the iterative repositioning of vertices, and offering a parameterisation aimed at fine-tuning this balance between crossings and execution time.
To go even further, a legitimate question is to ask what these algorithms would give when applied to different contexts, in particular when trying to represent graphs on surfaces other than the Euclidean plane. This paradigm shift brings new degrees of freedom for graph visualisation, especially in terms of crossing minimization, while at the same time raising new questions about how to adapt the mechanisms at work in a new representation model. We introduce two algorithms, one opting for a dynamic approach to graph drawing on the torus using force simulation, and another linking combinatorial and geometric representations of graphs on the Klein bottle.