Geometric Representations of Graphs

Ein Graph ist eine grundlegende kombinatorische Struktur, mit der man für eine Menge von Objekten (Knoten) repräsentieren kann, welche Paare von Objekten miteinander in Beziehung stehen (Kanten). Die Zeichnung eines Graphen ist eine Repräsentation des Graphen in der Ebene (oder auf einer anderen Oberfläche), bei der die Knoten typischerweise durch Punkte und die Kanten durch stetige Kurven zwischen den entsprechenden Knotenpaaren dargestellt werden. Solche Zeichnungen nennt man in der Visualisierungscommunity Knoten-Link-Diagramme.

Als Alternative zu Knoten-Link-Diagrammen kann man Knoten auch durch komplexere geometrische Objekte (z.B. Kreise, Rechtecke, etc.) darstellen. Entsprechend kann man Kanten entweder weiterhin durch Kurven zwischen ihren Endpunkten darstellen oder durch komplexere Interaktionen zwischen Paaren von Objekten – zum Beispiel als ihr Schnitt. Solche geometrischen Repräsentationen sind ein grundlegendes Thema in der diskreten Mathematik und in der Informatik, da sie häufig verwendet werden um Problemen der realen Welt zu modellieren.

Wir werden das Schnittmodell studieren und uns dabei auf mehrere verwandte Darstellungsprobleme konzentrieren: die Erweiterung partieller Repräsentationen, simultane Repräsentationen, Sichtbarkeitsrepräsentationen mit Hindernissen und H-topologische Schnittrepräsentationen. Auf dem Gebiet der geometrischen Graphen (also der Knoten-Link-Diagramme mit geradlinigen Kanten) werden wir zwei Parameter untersuchen, die in letzter Zeit vermehrt betrachtet wurden: die maximale Kreuzungszahl und die Ply-Zahl.