Inhaltszusammenfassung:
Planare Graphen bilden einen Eckpfeiler im Bereich der Graphenzeichnung mit einer reichhaltigen und vielfältigen Literatur, welche von kombinatorischen Ergebnissen bis hin zu algorithmischen Anwendungen, wie zum Beispiel dem effizienten Testen der Planarität oder der Berechnung eines Morphs zwischen zwei planaren Zeichnungen, reicht. Leider lassen sich dies grundlegenden Ergebnisse nicht ohne Weiteres auf mögliche Verallgemeinerungen planarer Graphen übertragen. Im ersten Teil der Arbeit befassen wir uns mit dieser Problematik und beschreiben Algorithmen, welche für Graphen mit kleiner Pfadweite effizient testen können, ob diese eine Zeichnung in der Ebene besitzen, in der jede Kante maximal k andere Kanten kreuzt. Außerdem entwicklen wir einen Algorithmus, der einen Morph für eine bedeutende Familie von 1-planaren Graphen berechnet (welches diesbezüglich das erste Resultat für Graphen mit nicht konstantem Geschlecht ist). Desweiteren entwerfen wir Algorithmen, welche für Graphen mit kleinem Grad eine RAC Zeichnung mit wenigen Knicken liefert. Im zweiten Teil der Arbeit untersuchen wir strukturelle Eigenschaften einiger Graphklassen im Forschungsgebiet "Beyond Planarity". Inspiriert von dem klassischen orthogonalen Zeichenstil führen wir zunächst eine Unterklasse von RAC- Graphen ein, für die wir die maximale Kantendichte, die Beziehung zu allgemeinen RAC-Graphen sowie das zugehörige Erkennungsproblem untersuchen. Im Anschluss zeigen wir eine obere Schranke für die Kantendichte von bipartiten gap-planaren Graphen, welche, bis auf eine konstante Anzahl an Kanten, bestmöglich ist. Außerdem betrachten wir die Klasse der fan-planaren Graphen, welche durch drei verbotene Kreuzungskonfigurationen definiert ist. Wir zeigen, dass das Zulassen oder Verbieten der dritten Konfiguration zu unterschiedlichen Klassen von Graphen führt und führen in diesem Sinne die Unterscheidung zwischen schwachen- und starken fan-planaren Graphen ein. Wir erweitern das Ergebnis der oberen Schranke der Kantendichte von starken zu schwachen fan-planaren Graphen und untersuchen außerdem die maximale Graphendicke von starken fan-planaren Graphen, welches die erste (nicht-triviale) Beziehung zwischen der Graphendicke und einer Graphklasse im Gebiet "Beyond Planarity" darstellt. Im letzten Teil der Arbeit führen wir ein algorithmisches Framework zur Visualisierung von Graphen ein, welches mehrere ästhetische Kriterien simultan optimieren kann. Der Hauptbeitrag unseres Frameworks besteht darin, dass es leicht auf zusätzliche Kriterien erweitert werden kann, da, im Gegensatz zu vielen anderen Algorithmen dieser Art, keine empirisch gefundenen Koeffizienten oder diferenzierbare Zielfunktionen benötigt werden.
Abstract:
Planar graphs form a cornerstone in the area of graph drawing with a rich and diverse literature ranging from combinatorial results to algorithmic applications such as the recognition problem of planar graphs or the existence of a morph between two planar drawings. Unfortunately, these seminal results do not easily extend to most proposed generalizations of planar graphs. In the first part of this thesis, we make progress in this direction and provide (approximation) algorithms to efficiently test if graphs of small pathwidth are k-planar, i.e., test if they can be drawn such that every edge is crossed at most k times. We further describe an algorithm that computes a morph for a meaningful family of 1-planar graphs, which is the first result in this direction for graphs of non-constant genus. We conclude the first part by considering the containment relation of low-degree graphs in the k-bend RAC setting by providing efficient drawing algorithms. In the second part, we study structural properties of beyond-planar graph classes. Motivated by the results from the previous chapter and inspired by orthogonal drawings, we introduce a subclass of RAC graphs for which we study the recognition problem, edge-density bounds and their relationship to general RAC graphs. We next consider the class of gap-planar graphs and establish a tight upper bound on the edge-density these graphs can obtain. We further consider fan-planar graphs, where we show that all three forbidden patterns which are used to define fan-planar graphs are in fact necessary (i.e., allowing or prohibiting each pattern gives rise to distinct classes of graphs). Whereas previous work showed that this is true for two of the three patterns, we explicitly consider the third pattern which gives rise to weak and strong fan-planar graphs. We establish edge-density bounds for the class of weak fan-planar graphs, thus extending previous results on strong fan-planar ones. We finally study the maximum thickness of strong fan-planar graphs and establish the first (non-trivial) relation between the graph thickness and a beyond-planar graph class. In the final part of this thesis, we provide an algorithmic framework for the simultaneous optimization of several aesthetic criteria which are characterized to be important in a good drawing. The main contribution of our algorithm is its ease of extension to additional criteria, since no empirically found coefficients or (surrogate) differentiable loss functions are required, which is common for other algorithms that optimize many such criteria in a joint way.
Fan-planarity