Geometrische Graphentheorie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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. Mit der geometrische Graphentheorie eng verwandt ist die topologische Graphentheorie.

Bekannt sind folgende Graphen und Probleme der geometrischen Graphentheorie:

  • 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.
  • Bei einem zufälligen geometrischen Graph liegen die Knoten gleichverteilt auf dem zugrundeliegenden Raum und sind genau dann verbunden, wenn ihre Distanz geringer ist als ein zuvor spezifizierter Parameter.
  • 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: C. A. Gorini (Hrsg.): Geometry at Work: Papers in Applied Geometry. Mathematical Association of America, Washington, DC 2000, S. 174–194.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Harv, Bandelt und Chepoi, 2008.