Textdokument
Neue Methoden für klassische Grapheinbettungsprobleme - Orthogonale Zeichnungen & bedingte Planarität
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2015
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Möchte man Graphen automatisiert möglichst anschaulich darstellen, so stößt man häufig auf anspruchsvolle Optimierungsprobleme, die diesen Visualisierungsproblemen zugrunde liegen. Ein gutes theoretisches Verständnis dieser Kernprobleme ist essentiell für den Entwurf von Algorithmen, die sowohl performant sind, als auch qualitativ hochwertige Visualisierungen generieren. Die in meiner Dissertation [Bl15] untersuchten Kernprobleme fallen in zwei Kategorieren und haben gemeinsam, dass sie zwar schon verhältnismäßig intensiv erforscht wurden (und damit als klassisch angesehen werden können), wohingegen gewissen zentrale Fragestellungen noch offen sind bzw. waren. Bei der ersten Kategorie handelt es sich um die Knickminimierung in orthogonalen Zeichnungen. Konkret wird der Fall betrachtet, dass die Topologie der Zeichnung nicht schon in der Eingabe gegeben ist (was mehr Freiheiten und damit bessere Ergebnisse zulässt, das Problem aber signifikant schwerer macht), sowie der Fall, dass die Knotengrade 4 überschreiten dürfen. Die zweite Kategorie beschäftigt sich mit dem Basisfall der Kreuzungsminimierung, also mit der Frage, ob ein Graph ganz ohne Kreuzungen (d.h. planar) gezeichnet werden kann. Dabei werden jedoch Szenarien betrachtet, in denen nicht nur ein einzelner Graph für sich visualisiert werden soll, sondern beispielsweise ein Graph zusammen mit einer Gruppierung (clustering) der Knoten oder zusammen mit einem zweiten Graphen auf der gleichen Knotenmenge (zum Vergleich verschiedener oder einer sich verändernden Relation auf den gleichen Objekten). Bei all diesen grundlegenden Problemen gehe ich der Frage nach, ob und unter welchen Voraussetzungen sie sich effizient (d.h. in polynomieller Zeit) lösen lassen.