Lydia Buntrock

Schnittgraphen geometrischer Objekte - Intersection Graphs of geometric objects

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 14.10.2014

Kurzbeschreibung

Die Schnittgraphen geometrischer Objekte sind ein interessanter Bestandteil der Graphentheorie, da sie eine Verbindung zur Geometrie schlagen und außerdem ein weitreichendes Feld an Anwendung, zum Beispiel in Genetik und Elektrotechnik, bieten.

Ein Schnittgraph (engl. intersection graph) ist ein Graph, der die Gestalt von Schnittpunkten einer Familie von Mengen darstellt. Wir betrachten Familien geometrischer Objekte in der Ebene und ordnen jeder Menge, das heißt jedem Objekt, einen Knoten zu und beschreiben eine Kante genau dann, wenn sich die betreffenden geometrischen Objekte berühren oder überlagern. Daher kann man Schnitt- graphen in das Feld der geometrischen Graphentheorie einordnen.

Wenn man beliebige Mengen zulässt, kann jeder Graph als Schnittgraph dargestellt werden. Betrachtet man jedoch Mengen bestimmter Kategorien, gibt es zu einigen Graphen keine Mengenfamilie in dieser Kategorie, welche den Graphen als Schnittgraphen hervorbringen. Diese Graphen müssen somit bezüglich dieser Kategorie bestimmte Eigenschaften erfüllen. Wir betrachten in dieser Arbeit Mengen von Intervallen, Kurven, Strecken und Kreisscheiben als geometrische Objekte.

Wir befassen uns in dieser Arbeit besonders mit den folgenden Fragestellungen bezüglich unseren geometrischen Objekten:

Wann ist ein gegebener Graph ein Schnittgraph beziehungsweise wie ist er charakterisiert?

Ist ein Graph ein Schnittgraph einer Art von geometrischen Objekten? Können wir einen Algorithmus angeben, um die Realisierung zu einem Schnittgraphen zu geben? Welche Laufzeit hat dieser?

Welche besonderen Eigenschaften haben die Schnittgraphen zu den gegebenen Objekten?