Graphzeichnen mit niedriger visueller Komplexität

Für das Zeichnen von Graphen gibt es eine Reihe von etablierten Kriterien, welche von einer gut lesbaren Zeichnung eines Graphen erfüllt werden sollten. So sollten Kreuzungen von Kanten möglichst vermieden werden, es sollten möglichst keine kleinen Winkel zwischen benachbarten oder kreuzenden Kanten auftreten, außerdem soll das Verhältnis zwischen dem größten und kleinsten Abstand aller Punktepaare möglichst klein sein. Im Idealfall sind Kanten durch Strecken dargestellt, mitunter aber auch durch Polygonzüge oder Kurven. Bei der Verwendung von Polygonzügen ist man darum bemüht, die Anzahl der Knicke zu minimieren.

In diesem Projekt soll ein neues Entwurfskriterium untersucht werden. Das Ziel ist es, eine Zeichnung mit möglichst wenig geometrischen Grundbausteinen zu erstellen. Zum Beispiel kann ein Kantenzug in einem Graphen als eine durchgehende Strecke dargestellt werden. Die Knoten werden dann ausschließlich durch Kreuzungen (oder durch Berührungspunkte) mit anderen geometrischen Elementen repräsentiert. Die Anzahl der Grundobjekte nennen wir die visuelle Komplexität der Zeichnung. Innerhalb des Projektes soll untersucht werden, wie man Zeichnungen mit niedriger visueller Komplexität erzeugen kann, und wo hierbei die Grenzen liegen. Diese Frage soll für verschiedene Klassen von planaren Graphen beantwortet werden, zum Beispiel für Bäume, serien-parallele Graphen, planare 3-Bäume und Triangulierungen. Als Grundelemente sollen in erster Linie Strecken und Kreisbögen verwendet werden.