Geometric graph theory

rdf:langString Geometrische Graphentheorie

rdf:langString 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 verknüpft sind. Mit der geometrische Graphentheorie eng verwandt ist die topologische Graphentheorie. Bekannt sind folgende Graphen und Probleme der geometrischen Graphentheorie: * Ein ebener Streckengraph ist ein Graph, der eine geradlinige Darstellung in der euklidischen Ebene hat. Der Satz von Wagner und Fáry besagt, dass jeder planare Graph als ebener Streckengraph realisiert werden kann. Eine Triangulierung ist ein ebener Streckengraph, zu dem keine Kanten mehr hinzugefügt werden können. Ein Spezialfall ist die Delaunay-Triangulierung – 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 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 (Satz von Balinski). 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 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 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 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 . Der besagt, dass die Schnittgraphen von sich nicht überschneidenden Kreisen genau die planaren Graphen sind. Die 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 führen zu vielen wichtigen symmetrischen Graphen und . * Der 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 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 , können als partielle Würfelgraphen repräsentiert werden. Ein wichtiger Spezialfall eines partiellen Würfels ist das Gerüst eines . 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 , haben verwandte Definitionen, die metrische Einbettungen erfordern. * Ein 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 , und für höherdimensionale Triangulierungen zu definieren. Der Flip-Graph von Triangulierungen eines konvexen Polygons bildet das Gerüst des (oder Stasheff-Polytops). Der Flip-Graph einer Punktmenge (Projektionen höherdimensionaler konvexer Hüllen) kann ebenfalls als Gerüst von dem sogenannten 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.