Engineering human-in-the-loop graph drawing algorithms : A study of vertex splittingand semantic word clouds

Abstract

Algorithms are central to our daily lives, but there exist a large number of problems for which they are insufficient. To undertake these problems, we consider in this thesis combining a human's expert knowledge with the computing power of the machine through human-in-the-loop algorithm design. We find that graph drawing is a natural application of this paradigm, as it combines a strong focus on aesthetic optimization goals, with hard computational problems. We examine traditional node-link diagrams, specifically computing drawings with a low number of crossings. We consider vertex splitting, where we replace a vertex by copies of itself, and partitions the neighborhood of the split vertex between its copies. We stud this operation in the context of general graph drawings as well as in outerplanar and bipartite graphs. We also inspect these findings towards empirical applications. We then focus on word clouds, where, given an input text, one should compute a layout of the words in the plane, in which words are scaled according to their frequency. We study the semantic variation of word clouds, where the task for the layout is to reflect the the semantic closeness of the words in the input text, by placing related words in close proximity. We identify tractable restrictions to this problem and finally, we investigate layout algorithms that combine the machine's computing abilities with the user's personal aesthetic preferences, develop a tool, and evaluate it through a user study.