Geometrische Graphentheorie

Die geometrische Graphentheorie ist ein spezieller Zweig der Graphentheorie, der sich mit der Untersuchung geometrischer Graphen beschäftigt. Ein geometrischer Graph ist ein Graph, bei dem Knoten oder Kanten mit geometrischen Objekten oder Konfigurationen verknüpft sind. Bekannt sind folgende Graphen und Probleme der geometrischen Graphentheorie:

• Ein ebener Streckengraph ist ein Graph, bei dem die Knoten als Punkte in der euklidischen Ebene und die Kanten als sich nicht überschneidende Geradenstücke eingebettet sind. Der Satz von Fáry besagt, dass jeder planare Graph eine Repräsentation als ebener Streckengraph besitzt. Eine Triangulierung ist ein ebener Streckengraph, zu dem keine Kanten mehr hinzugefügt werden können. Ein Spezialfall ist die Delaunay-Triangulation – ein Graph der aus einer Menge von Punkten in der Ebene entsteht, indem man immer dann zwei Punkte mit einer Kante verbindet, sobald ein Kreis existiert, der nur diese zwei Punkte enthält.

• Das 1-Gerüst eines Polyeders oder Polytops ist die Menge der Knoten und Kanten des Polytops. Das Gerüst eines konvexen Polyeders ist immer ein planarer Graph, und das Gerüst eines k-dimensionalen konvexen Polytops ist immer ein k-fach knotenzusammenhängender Graph. Umgekehrt besagt der Satz von Steinitz, dass jeder 3-zusammenhängende planare Graph das Gerüst eines konvexen Polyeders ist. Von daher werden Graphen dieser Klasse auch als Polyedergraphen bezeichnet.

• Ein euklidischer Graph ist ein Graph, bei dem die Knoten durch Punkte in der Ebene repräsentiert werden, und bei dem den Kanten der euklidische Abstand zwischen diesen Punkten zugeordnet wird. Der euklidische minimale Spannbaum ist der minimale Spannbaum eines euklidischen vollständigen Graphen. Es ist auch möglich, Graphen anhand von Abstandsbedingungen zu definieren. Insbesondere bildet man einen Einheitsdistanz-Graphen, indem man gleichentfernte Punkte miteinander verbindet. Das Hadwiger–Nelson-Problem beschäftigt sich mit der chromatischen Zahl dieser Graphen.

• Ein Schnittgraph ist ein Graph, bei dem jeder Knoten mit einer Menge assoziiert wird und bei dem Knoten durch Kanten verbunden werden, wenn die entsprechenden Mengen einen nichtleeren Schnitt bilden. Sind die Mengen geometrische Objekte, erhält man als Ergebnis einen geometrischen Graphen. Beispielsweise ist der Schnittgraph von Geradenstücken in der ersten Dimension ein Intervallgraph und der Schnittgraph von Einheitsscheiben in der Ebene ein Einheitscheiben-Graph. Der Kreispackungssatz besagt, dass die Schnittgraphen von sich nicht überschneidenden Kreisen genau die planaren Graphen sind. Die Scheinermann-Vermutung besagt, dass jeder planare Graph als Schnittgraph von Geradenstücken in der Ebene repräsentiert werden kann.

• Ein Levi-Graph einer Familie von Punkten und Geraden hat einen Knoten für jedes dieser Objekte und eine Kante für jedes inzidente Punkt-Geraden-Paar. Levi-Graphen projektiver Konfigurationen führen zu vielen wichtigen symmetrischen Graphen und Käfigen.

• Der Sichtbarkeitsgraph eines geschlossenen Polygons verbindet ein Knotenpaar mit einer Kante, wenn das entsprechende Geradenstück vollständig im Polygon enthalten ist. Bisher ist kein effizienter Test dafür bekannt, ob ein ungerichteter Graph durch einen Sichtbarkeitsgraphen repräsentiert werden kann.

• Ein partieller Würfel ist ein Graph, bei dem die Knoten mit den Knoten eines Hyperwürfels assoziiert werden, und zwar so, dass die Abstände in dem Graphen mit den Hamming-Distanzen zwischen den entsprechenden Hyperwürfel-Knoten übereinstimmen. Viele wichtige Familien kombinatorischer Strukturen, wie die der azyklischen Orientierungen eines Graphen oder die Nachbarschaft zwischen Regionen in einer Hyperebenen-Anordnung, können als partielle Würfelgraphen repräsentiert werden. Ein wichtiger Spezialfall eines partiellen Würfels ist das Gerüst eines Permutoeders. Dabei handelt es sich um einen Graphen, bei dem Knoten Permutationen einer Menge von geordneten Objekten und Kanten Vertauschungen von aufeinanderfolgenden Objekten repräsentieren. Viele weitere wichtige Graphenklassen, einschließlich Median-Graphen, haben verwandte Definitionen, die metrische Einbettungen erfordern.^[1]

• Ein Flip-Graph wird von den Triangulierungen einer Punktmenge gebildet, bei der jeder Knoten eine Triangulierung repräsentiert und zwei Triangulierungen mit einer Kante verbunden sind, falls diese sich durch die Versetzung einer Kante voneinander unterscheiden. Es ist auch möglich ähnliche Flip-Graphen für Unterteilungen in Vierecke oder Pseudodreiecke, und für höherdimensionale Triangulierungen zu definieren. Der Flip-Graph von Triangulierungen eines konvexen Polygons bildet das Gerüst des Associaeders (oder Stasheff-Polytops). Der Flip-Graph regulärer Triangulierungen einer Punktmenge (Projektionen höherdimensionaler konvexer Hüllen) kann ebenfalls als Gerüst von dem sogenannten Sekundärpolytop repräsentiert werden.

Siehe auch

• Chemische Graphentheorie

Literatur

• Hans-Jürgen Bandelt, Victor Chepoi: Metric graph theory and geometry: a survey. In: Contemp. Math.. 2008 (online).

• János Pach: Towards a Theory of Geometric Graphs. Contemporary Mathematics, no. 342, American Mathematical Society, 2004.

• Tomaž Pisanski, Milan Randić: Bridges between geometry and graph theory. In: Geometry at Work: Papers in Applied Geometry. Mathematical Association of America, Washington, DC 2000, S. 174–194 (online).

Einzelnachweise

1. ↑ Harv, Bandelt und Chepoi, 2008.