Forschungsthemen

Auf dem Gebiet des Graphenzeichnens beschäftigt man sich damit, wie man einen gegebenen Graphen möglichst gut zeichnen kann. Hierbei gibt es verschiedene Entwurfskriterien, was in diesem Zusammenhang mit "gut" gemeint ist. Wichtig ist auf jeden Fall, dass die Zeichnung lesbar ist. Das heißt unter anderem, dass man möglichst wenige Kreuzungen von Kanten zulassen will. Außerdem möchte man kleine Winkel und (nach Normierung) kleine Kantenlängen vermeiden.

Im Allgemeinen ist es sehr schwierig diese Probleme optimal zu lösen. Es gibt jedoch auch eine Reihe von Graphklassen für die gute Zeichnungen effizient berechnet werden können. Die Vielzahl der relevanten Graphklassen, verschiedene Zeichenstile und die Kombinationsmöglichkeiten bei den Entwurfskriterien erzeugen eine Vielzahl von interessanten Fragestellungen. Das Lehrgebiet setzt seine Schwerpunkte innerhalb des Graphenzeichnens auf folgende Themen:

• Zeichnen von Graphen mit Kreisbögen
• Zeichnen von Graphen als Arrangement mit niedriger Grundmenge
• Konstruktion von Zeichnungen mit vielen monotonen Pfaden
• Empirische Verifizierung von theoretisch begründeten Entwurfskriterien

Auf dem Gebiet der abzählbaren Kombinatorik untersuchen wir, wie viele Strukturen in einem Graphen enthalten sein können (bzw. auf einer Punktmenge realisiert werden können). Meist sind hier obere und untere Schranken für die maximale Anzahl von Interesse. Typische Strukturen die man betrachtet sind (Hamilton) Kreise, Spannbäume, Matchings, oder Wälder. Die Frage nach der Anzahl ist immer dann von Interesse, wenn es mangels eines effizienten Algorithmus notwendig ist, die gesamte protentielle Lösungsmenge eines Problems zu durchsuchen (zum Beispiel Hamiltonkreise beim Rundreiseproblem). In diesem Fall kann man mit Hilfe der Schranken für die Maximalanzahl Aussagen über die worst-case Laufzeit treffen. Folgende Kombinationen sind unter diesen Gesichtspunkten besonders interessant:

• Wieviele Kreise sind maximal in einem planaren Graphen enthalten?
• Wieviele Hamiltonkreise kann ich kreuzungsfrei auf einer Punktmenge realisieren, und wie sieht die Punktmenge in diesem Fall aus?