Textdokument
The Many Faces of Planarity – Matching, Augmentation, and Embedding Algorithms for Planar Graphs
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Ein Graph ist planar, wenn er sich kreuzungsfrei in die Ebene zeichnen lässt. Planarität ist eine zentrale Eigenschaft, nicht nur im Graphenzeichnen, sondern in der gesamten Graphentheorie. Oftmals lassen sich für planare Graphen stärkere theoretische Aussagen beweisen und effizientere Algorithmen angeben als für allgemeine Graphen. Andererseits tritt Planarität oft auch als Nebenbedingung auf und macht Probleme dadurch schwieriger. Eine besondere Rolle spielen planare Graphen in der Visualisierung, da Kreuzungen die Lesbarkeit von Zeichnungen verschlechtern. In der vorliegenden Dissertation [Rut11] untersuche ich eine Reihe von Problemen, in denen Planarität auf unterschiedliche Weise auftritt. Im Bereich der kombinatorischen Optimierung wird Planarität als Nebenbedingung für Graphaugmentierungsprobleme sowie als Eingaberestriktion für Matching-Probleme betrachtet und beleuchtet inwiefern dies die Komplexität der jeweiligen Probleme verändert. Der zweite Teil der Arbeit befasst sich mit der Visualisierung planarer Graphen. Bisherige Verfahren zur planaren Visualisierung legen häufig zunächst eine kombinatorische Einbettung fest und optimieren dann im Rahmen dieser Einbettung weitere ästhetische Kriterien. Die Einschränkung auf eine einzige anfangs gewählte Einbettung erweist sich dabei häufig als nachteilig. Ich stelle Verfahren vor, die es ermöglichen über alle Einbettungen eines planaren Graphen zu optimieren und unter allen Einbettungen eine zu finden, die für die Visualisierung am besten geeignet ist.