Graphs are formal models to represent relations between objects. Drawings provide intuitive interactions between humans and models. Unfortunately, the multidimensional information associated to a graph cannot be easily visualized in two dimensions. Thus, the problem of graph drawing consists in providing 2D projections as informative as possible.
The main challenge of graph drawing is to transfer visual information that maximizes the knowledge our brain can acquire from a pictorial representation. But the mechanisms used by our brain for information processing are not well understood yet. Here is where the concept of graph aesthetics arises as a means to provide quantifiable metrics that have a correlation with the subjective concept of beauty in a graph visualization.
Different graph aesthetics have been proposed in the literature (e.g., see here), including some work to evaluate their cognitive cost: edge crossings, edge lengths, crossing angles, path continuity, etc. These metrics are approximations to the concept of beauty based on experimental tests.
Below you can see the layouts of three different graphs that have been obtained using a combination of spectral algorithms (using eigenvectors) and force-directed placement. Each one has different aesthetics. One of the metrics to assess about the quality of the visualization is the number of edge crossings (the smaller, the better). |
 |
 |
The goal of this project is to provide estimators of different graph aesthetic metrics (e.g., edge crossings) by studying the structure of the graph before applying any drawing algorithm. Machine learning based on graph centralities, embeddings and graph neural networks will be used to obtain good estimators.
The project will use the graph drawing algorithms and graph centralities provided by NetworkX.