Graphzeichnen mit niedriger visueller Komplexität

• Antragsteller: Professor Dr. André Schulz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 256873462

Dieses Projekt widmet sich einem neuen Entwurfskriterium für das automatisierte Zeichnen von Graphen. Man erwartet von der Zeichnung eines Graphen, dass sie eine lesbare und leicht verständliche Darstellung liefert. Das beinhaltet unter anderem, dass die einzelnen Knoten und Kanten für den Betrachter gut zu unterscheiden sind. Im klassischen Sinne bilden Kanten und Knoten die Grundelemente der Zeichnung die es geeignet anzuordnen gilt. Innerhalb des Projektes soll sich damit beschäftigt werden, wie man Zeichnungen erzeugen kann, die aus möglichst wenig Grundelementen zusammengesetzt sind. Die Idee hierbei ist, dass man einen Kantenzug im Graphen durch ein einzelnes Objekt darstellen kann. Dadurch ist es möglich weniger Grundelemente zu benutzen, als die Zeichnung Kanten hat. Die Zeichnung entspricht demnach einem Arrangement, dessen Graph gerade der zu zeichnende Graph ist. Die Anzahl der Grundelemente der Zeichnung nennen wir ihre visuelle Komplexität. Als Grundelemente betrachten wir in erster Linie Strecken und Kreisbögen. Bei den zu zeichnenden Graphen konzentrieren wir uns auf planare Graphen. Als Sonderfälle betrachten wir Bäume, serien-parallele Graphen, außerplanare Graphen, planare 3-Bäume und Triangulierungen.Im Projekt sollen Algorithmen entworfen werden, die Zeichnungen mit niedriger visueller Komplexität erzeugen. Klassische Entwurfsziele sollen dabei nicht verletzt werden. Zur Einschätzung der Qualität der Zeichnungen soll analysiert werden, wie groß die visuelle Komplexität eines Graphen im schlechtesten Fall in Abhängigkeit zur Anzahl seiner Kanten sein kann. Aus dieser Fragestellung leiten sich eine Reihe von kombinatorischen Problemen auf dem Gebiet der Graphentheorie ab, denen sich in diesem Projekt gewidmet werden soll. Die These ob Zeichnungen mit niedriger visueller Komplexität ästhetisch ansprechend sind und eventuell andere Vorteile gegenüber klassischen Zeichnungen besitzen, soll an Hand von empirischen Benutzerstudien überprüft werden. Zusätzlich soll der Zusammenhang zwischen Zeichnungen mit niedriger visueller Komplexität und Kontakt-Repräsentationen von Kreisbögen untersucht werden.

• DFG-Verfahren: Sachbeihilfen