Geometrische Graphentheorie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.
  • 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.
  • 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[Bearbeiten]

Literatur[Bearbeiten]

  •  Hans-Jürgen Bandelt, Victor Chepoi: Metric graph theory and geometry: a survey. In: Contemp. Math.. 2008 (online (PDF; 377 kB)).
  •  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 (PDF; 704 kB)).

Einzelnachweise[Bearbeiten]

  1. Harv, Bandelt und Chepoi, 2008.