Eliminierung von Schnittpunkten in Zeichnungen von Graphen

Graphen (oder Netzwerke) sind allgegenwärtige mathematische Strukturen, die paarweise Wechselwirkungen (Kanten) zwischen Objekten (Ecken oder Knoten des Graphen) beschreiben. Das Studium großer Graphen ist von zunehmender Bedeutung in der Biologie, der Bioinformatik, der Finanzwirtschaft, der Soziologie und vielen anderen wissenschaftlichen Gebieten. In Anwendungen sind Graphen oft abstrakt, durch eine Liste von Ecken und und Kanten beschrieben, und um sie besser zu verstehen, ist es essentiell, sie visuell darzustellen. Das gängigste mathematische Modell zur Visualisierung sind Zeichnungen, wobei die Ecken eines Graphen durch Punkte in der Ebene dargestellt werden und Kanten durch Kurven, die die entsprechenden Endpunkte verbinden. Die zunehmende Nachfrage nach Software, um große Graphen zu visualisieren, treibt die Forschung an Algorithmen voran, um Zeichnungen großer Graphen automatisch zu generieren. Weitere Impulse für diese Forschungsrichtung werden seit den 1980er Jahren durch Anwendungen wie das Design von Computerchips gegeben. Je nach Anwendung muss eine gewünschte Visualisierung des Graphen bestimmte Qualitätsmaße erfüllen. Ein besonders wichtiger Parameter ist die Anzahl der Kreuzungen, deren Minimierung eine der entscheidenden mathematischen Herausforderungen in der automatisierten Visualisierung von Graphen darstellt. Das hier vorgeschlagene Projekt verfolgt zweierlei Ziele. Einerseits wollen wir mathematische Methoden für den Entwurf von schnellen Algorithmen für Graphenzeichnungen entwickeln, die die Anzahl der Kantenkreuzungen unter zusätzlichen Einschränkungen minimieren. Unser Ansatz basiert entscheidend auf dem Hanani-Tutte-Paradigma, welches den Nachweis der Existenz der gewünschten kreuzungsfreien Zeichnung eines Graphen auf das algebraische Problem der Lösung eines linearen Gleichungssystems reduziert. Andererseits wollen wir mehrere grundlegende ungelöste Probleme über höherdimensionale Analoga von Graphen und in der Ebene oder auf komplizierteren Flächen gezeichnete Graphen angehen, deren Lösung in den Bereichen der Graphenvisualisierung sowie der kombinatorischen und algorithmischen Geometrie wesentliche neue Impulse geben würde. Einige der grundlegenden, intuitiv zugänglichen Fragestellungen, mit denen wir uns beschäftigen werden, sind die folgenden: Was ist die minimale Anzahl von Kreuzungen (Kreuzungszahl) in einer Zeichnung eines gegebenen Graphen in der Ebene? Ist diese Zahl immer dieselbe wie die minimale Anzahl von Paaren von Kanten, die sich kreuzen (Paarkreuzungszahl)? Überraschenderweise ist es seit Jahrzehnten offen, ob es einen Graphen gibt, für den sich diese Zahlen unterscheiden. Unter einem Thrackle versteht man einen Graphen, der so in der Ebene gezeichnet werden kann, dass sich jedes Kantenpaar genau einmal trifft: Entweder in einem gemeinsamen Endpunkt, oder in einer echten Kantenkreuzung. Es ist seit fast einem halben Jahrhundert offen, ob ein Thrackle mehr Kanten als Knoten haben kann.

Die Entwicklung automatisierter, grafisch lesbarer Visualisierungen ist mit zahlreichen Herausforderungen verbunden. Die Herausforderungen sind auf widersprüchliche Qualitätsmaße zurückzuführen, die eine gewünschte Visualisierung erfüllen muss, beispielsweise die Lesbarkeit gegenüber der Gesamtheit der Darstellung oder die Größe der Merkmale gegenüber der Gesamtgröße. Wir konzentrieren uns auf den Kompromiss zwischen der Lesbarkeit und der Gesamtheit der Darstellung. Große Netzwerke, die in Anwendungen mit Millionen von Knoten und Verbindungen zwischen diesen entstehen, sind unlesbar, wenn sie vollständig dargestellt werden. Ohne die Gesamtheit zu beeinträchtigen, entsteht ein unlesbares Durcheinander. Eine brauchbare Lösung für dieses Problem besteht darin, das Diagramm mit einer Hierarchie von Clustern auszustatten und zu jedem Zeitpunkt nur lokal verwandte Cluster zu visualisieren. Um die Lesbarkeit von Visualisierungen von Graphen noch weiter zu verbessern, möchten wir die Anzahl der Kreuzungen zwischen den Kurven minimieren, was eine der wichtigsten Herausforderungen bei der automatisierten Visualisierung von Graphen darstellt. Motiviert durch diese Überlegungen untersuchten wir graphen-basierte Strukturen, sogenannte Obstruktionen, die Kreuzungen in beliebigen Darstellungen auf Flächen wie Ebene, Torus, Doppeltorus usw. erzwingen. Als eine unserer wichtigsten Errungenschaften haben wir bewiesen, dass ein gewisser, eleganter Ansatz zur Identifizierung von Hindernissen auf komplizierten Oberflächen nicht funktioniert. Ein weiteres Hauptergebnis unserer Arbeit ist der erste schnelle Algorithmus für die sogenannte "Clustered Planarity". Die Existenz eines Polynomialzeit- Algorithmus für Clustered Planarity war seit langem ein bekanntes offenes Problem in der theoretischen Informatik. Unser Algorithmus bestimmt, ob ein mit einer hierarchischen Gruppierung ausgestatteter Graph ohne Überkreuzungen dargestellt werden kann, wobei die gegebene Gruppierung in einem bestimmten natürlichen Sinne beachtet wird. Wir glauben, dass der Algorithmus und seine Varianten als Grundbaustein für ein automatisiertes Visualisierungssystem für Graphen geeignet ist.