AbstractsBiology & Animal Science

Graphenzeichnen ist ein Bereich der Informatik mit langer Tradition. Insbesondere im Bereich des orthogonalen Graphenzeichnens wird seit den 1980er Jahren motiviert durch VLSI-Design (Chip-Design) und Grundrissplanung intensiv geforscht. In dieser Arbeit wird das klassische orthogonale Modell durch neue Elemente, unter anderem aus dem oktilinearen Graphenzeichnen, erweitert. Die ersten Ergebnisse, die wir in dieser Arbeit vorstellen, befassen sich mit oktilinearem Graphenzeichnen. Dieses Modell ist altbekannt und viele Aspekte wurden schon untersucht. Wir entwickeln eine Methode mit der für planare Graphen mit einem beschränkten maximalen Knotengrad (4 und 5) Zeichnungen mit maximal einem Knick pro Kante erstellt werden können. Außerdem zeigen wir, dass Graphen mit maximalem Knotengrad 6 nicht immer mit einem Knick pro Kante gezeichnet werden können. Damit schließen wir die Lücke zwischen bekannten Ergebnissen, die besagen dass Graphen mit maximalem Knotengrad 3 immer ohne Knicke und alle Graphen bis zu einem maximalen Knotengrad von 8 mit höchstens zwei Knicken pro Kante oktilinear gezeichnet werden können. Durch Nutzerstudien konnte gezeigt werden, dass die Lesbarkeit von (Graphen) Zeichnungen durch Knicke auf den Kanten und schlecht identifizierbare Kreuzungen besonders beeinträchtigt wird. An diesem Punkt setzt unser neues Modell, das abgeschrägt orthogonale (engl. slanted orthogonal, oder kurz: slog) Graphenzeichnen an. Im slog Modell ist der kleinste erlaubte Winkel zwischen zwei aufeinander folgenden Kantensegmenten 135°. Das hat zur Folge, dass slog Zeichnungen keine normalen Knicke mehr haben, sondern sogenannte Halb-Knicke. Um Kreuzungen besser erkennbar zu machen sind im slog Modell Kreuzungen ausschließlich zwischen diagonalen Segmenten erlaubt. Wir zeigen, dass eine knick-minimale slog Zeichnung mindestens doppelt so viele Halb-Knicke benötigt, wie eine knick-minimale orthogonale Zeichnung Knicke hat. Für das slog Modell werden in dieser Arbeit Methoden zur Berechnung von knick-minimalen Zeichnungen vorgestellt. Da diese exponentielle Fläche benötigen können, wird außerdem eine Heuristik entwickelt, die nur quadratische Fl ̈ache benötigt, dafür aber mehr Knicke zulässt. Die Ergebnisse einer experimentellen Evaluation des slog Modells werden ebenfalls präsentiert. Im Anschluss erweitern wir das slog Modell zu einer flexibleren Variante die wir sloggy nennen. Das sloggy Modell hat alle Eigenschaften des slog Modells, aber Kreuzungen werden jetzt auch zwischen orthogonalen Segmenten erlaubt. Dafür wird die Anzahl Halb-Knicke beschränkt auf genau zwei Mal die Anzahl Knicke der entsprechenden knick-minimalen orthogonalen Zeichnung. Außerdem wird die Anzahl an Kreuzungen zwischen diagonalen Segmenten maximiert. Wir entwickeln eine Methode zur Berechnung solcher Zeichnungen und zeigen, dass auch hier exponentielle Fläche benötigt werden kann. Das slog und das sloggy Modell sind auf Graphen mit einem maximalen Knotengrad von 4 beschränkt. Deswegen wenden wir uns als nächstes…