On this page, you can find my Master’s Thesis, supplementary material and errata.
Visualizing relational data as drawing of graphs is a technique in very wide-spread use across many fields and professions. While many graph drawing algorithms have been proposed to automatically generate a supposedly high-quality picture from an abstract mathematical data structure, the graph drawing community is still searching for a way to quantify the aesthetic value of any given solution in a way that allows one to compare graph layouts created by different algorithms for the same graph (presumably to automatically choose the better one). We believe that one promising path towards this goal could be enabled by combining data analysis techniques that have proven useful in other scientific disciplines that are dealing with large structures such as astronomy, crystallography or thermodynamics. In this work we present an initial investigation of some statistical properties of graph layouts that we believe could provide viable syndromes for the aesthetic value. As a proof of concept, we used machine learning techniques to train a neural network with the results of our data analysis and thereby built a model that is able to discriminate between better and worse layouts with an accuracy of 95 %. A rudimentary evaluation of the model was performed and is presented. This work primarily provides an infrastructure to enable further experimentation on the topic and will be made available to the public as Free Software.
This work may be cited as:
Moritz Klammler, Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification. Master’s thesis, Karlsruhe Institute of Technology, 2018. https://klammler.eu/msc/
The following BibTeX entry might come handy:
@Thesis{Klammler2018,
author = "Klammler, Moritz",
title = "Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification",
school = "Karlsruhe Institute of Technology",
year = "2018",
month = "3",
type = "master's thesis",
address = "Karlsruhe, Germany",
url = "https://klammler.eu/msc/",
}
Development of the code that was written during the preparation of this thesis was continued after submission and has been publised on GitHub.
We also submitted a paper to GD’18 which – as it so happens –
has won a Best Paper Award
. You can download the extended version
of the paper from
arXiv.
The presentation slides for the talk given at the conference are
available
here.
Note that you can find the source code for all publications in the
public repository mentioned above.
ANGULAR property using the
described algorithm of a graph with n vertices and
m edges is
Ο(m log(m)) ⊆
Ο(n2 log(n))
in the worst case (of a fully connected graph) and not
Ο(m) as stated in the thesis. The
logarithmic factor is due to the sorting of the polar angles.