Ungerichteter Graph/Geometrische Realisierung/Dreidimensional/Textabschnitt

Ein ungerichteter Graph ${}G=(V,E)$ lässt sich stets dreidimensional realisieren, d.h. durch eine überschneidungsfreie geometrische Realisierung im ${}\mathbb {R} ^{3}$. Dafür gibt es mehrere Möglichkeiten, wobei wir hier die Ideen beschreiben und auf eine detaillierte Begründung verzichten. Da jeder Graph ein Untergraph eines vollständigen Graphen ist, und eine geometrische Realisierung eines Graphen direkt durch Weglassen von stetigen Wegen eine geometrische Realisierung eines Untergraphen ergibt, muss man lediglich begründen, dass man die vollständigen Graphen dreidimensional realisieren kann.

Man legt die ${}n$ Punkte auf eine Kreissphäre in der Ebene. Dann verbindet man den ersten Punkt mit den anderen Punkten durch gerade Strecken. Den zweiten Punkt verbindet man mit den weiteren (ab dem dritten) Punkten durch „Schnüre“ (mit einer gewissen Dicke), die über den schon liegenden Strecken verlaufen und ansonsten gestreckt sind. Den dritten Punkt verbindet man mit den weiteren Punkt durch Schnüre, die über den schon verwendeten Schnüren liegen, u.s.w. Die stetigen Wege kann man dann in der Querschnittsmitte der Schnüre realisieren.

Man platziert die Punkte auf einer Geraden und betrachtet im Raum hinreichend viele Halbebenen (Seiten eines Buches), die an dieser Geraden anliegen. Jetzt kann für jedes Punktepaar, das man verbinden möchte, einen Verbindungsbogen in einer dafür gewählten Halbebene zeichnen.

Man platziert die ${}n$ Punkte ${}P_{i}$, ${}i=1,\ldots ,n$, in der Ebene

${}\mathbb {R} ^{2}\times \{0\}\subseteq \mathbb {R} ^{3}\,.$

Es sei ${}\epsilon >0$ derart, dass die ${}\epsilon$-Umgebungen der Punkte zueinander disjunkt sind. Sei ${}m={\binom {n}{2}}$. Man platziert nun in der ${}\epsilon$-Umgebung von einem jeden Punkt ${}P_{i}$ jeweils ${}n$ Punkte ${}Q_{ij}$ (Liftungspunkte) und setzt diese in die Ebene

${}\mathbb {R} ^{2}\times \{m\}\subseteq \mathbb {R} ^{3}\,.$

Der Punkt ${}P_{i}$ wird durch gerade (ziemlich vertikale) Strecken ${}V_{ij}$ mit seinen ${}n$ Liftungspunkten verbunden. Diese Verbindungsstrecken liegen allesamt im Schlauch ${}U{\left(P_{i},\epsilon \right)}\times [0,m]$. Zu jedem Punktepaar ${}P_{i}\neq P_{j}$ gehört eine Ebene ${}\mathbb {R} ^{2}\times {\ell }$, ${}\ell =1,\ldots ,m$. Die Punkte ${}P_{i}$ und ${}P_{j}$ werden nun dadurch miteinander verbunden, dass man von ${}P_{i}$ aus entlang ${}V_{ij}$ und von ${}P_{j}$ aus entlang ${}V_{ji}$ jeweils bis zum Durchstoßungspunkt mit der ${}\ell$-Ebene hochgeht. Die beiden Durchstoßungspunkte werden dann horizontal in der ${}\ell$-Ebene durch eine gerade Strecke verbunden. In dieser Konstruktion werden alle Punkte miteinander überschneidungsfrei verbunden, da die Verbindungswege nur in den Schläuchen und in den verschiedenen Ebenen verlaufen.

Man ordnet die ${}n$ Knotenpunkte auf einer Kugeloberfläche an und verbindet je zwei Punkte durch „Fäden“. Dabei dürfen die Fäden im Allgemeinen nicht völlig straff sein. Wenn man die Punkte durch gerade Strecken verbinden möchte, so kann es bei einer gegebenen Punktkonfiguration auf der Kugeloberfläche zu Überschneidungen kommen. Diese kann man jedoch auch dadurch wegkriegen, dass man die einzelnen Punkte auf der Kugeloberfläche etwas bewegt. Dass dies möglich ist, beweist man durch Induktion über die Anzahl ${}n$. Es seien also ${}n$ Punkte auf der Kugeloberfläche gegeben mit der Eigenschaft, dass die Streckenverbindungen zu je zwei Punkten sich nicht treffen (außer in den Punkten selbst), und es soll noch ein weiterer Punkt hinzugenommen werden derart, dass auch die neuen Verbindungsstrecken dieses neuen Punktes mit den zuvor gegebenen Punkten keine Überschneidungen mit den alten Verbindungsstrecken besitzt. Ein alter Punkt ${}u$ und die Verbindungsstrecke zu zwei alten Punkten ${}v$ und ${}w$ (wichtig ist nur der Fall, wo diese Punkte verschieden sind) liegt in der durch ${}u,v,w$ definierten Ebene ${}F$ im Raum. Diese Ebene schneidet die Kugeloberfläche in einer Kreissphäre, und auf dieser darf der neue Punkt nicht liegen. Da es nur endlich viele Dreierpaare gibt, gibt es nur endlich viele Ebenen bzw. Sphären, die man ausschließen muss.

Aus einer hochdimensionalen geometrischen Realisierung eines Graphen wie der Standardrealisierung kann man durch eine generische (orthogonale) Projektion auf einen niedrigerdimensionalen Unterraum der Dimension ${}\geq 3$ eine weitere geometrische Realisierung erhalten. Die Projektionsrichtung muss dabei so gewählt sein, dass zwei Punkte nicht identifiziert werden und dass keine Überkreuzungen entstehen.