Abschlussvortrag: On Layered Area-Proportional Rectangle Contact Representations

Betreuer: Jun.-Prof. Dr. Philipp Kindermann (Uni Trier), Prof. Dr. Heinz Schmitz

Abstract:
Word clouds are a popular tool to analyze a given text. They arrange the most frequent words of a text in a visually pleasing way and scale words according to their importance. They are, however, prone to misinterpretation, especially in the sense that words that are placed closely together are perceived to be related, even though that is not necessarily the case.This is where semantic word clouds come into play.
Semantic word clouds do place semantically related words more closely together than words that are not related and thus fulfill the natural expectations of those examining the word clouds.
When formalized, the problem of drawing semantic word clouds reduces to drawing a rectangle contact representation of a graph whose vertices correlate to the words to be displayed and whose (weighted) edges indicate the semantic relatedness of two given words.
In this thesis, we consider a variant of this problem that restricts input graphs to be layered and internally triangulated and all rectangles to be of equal height, which we call MAXIMUM LAYERED CONTACT REPRESENTATION OF WORD NETWORKS or  MAX LAYERED-CROWN, as well as the variant MAX INT-LAYERED-CROWN, which restricts the problem to only rectangles of integer width and placement of those rectangles to integer coordinates.
Specifically, we classify the corresponding decision problem INT-LAYERED-CROWN as NP-complete and introduce three algorithms: Two of them are approximation algorithms, one solving MAX LAYERED-CROWN with a constant approximation factor, the other one a polynomial-time approximation scheme for MAX INT-LAYERED-CROWN. The latter uses the third algorithm, a dynamic program,  which classifies MAX INT-LAYERED-CROWN as a member of XP, as a subroutine.