Als planarer Graph wird derjenige Graph bezeichnet, der sich in der Ebene darstellen lässt ohne dass sich zwei Kanten des Graphen schneiden. Die ersten Überlegungen zur Planarität finden sich bereits bei Euler und seinem berühmten Polyedersatz. In den letzten Jahrzehnten, insbesondere durch die Entwicklungen im Bereich der Mikrochips (VLSI), wurde die Frage nach der planaren Darstellung eines Graphen immer relevanter. Weitere Anwendungen finden sich in sämtlichen Bereichen in denen Leitungen oder Transportwege (Kanten) zwischen verschiedenen Standorten bzw. Quellen und Senken (Knoten) überschneidungsfrei in einer Ebene gezeichnet bzw. verlegt werden müssen.
Zunächst stellt sich allerdings die Frage, ob für einen gegebenen Graphen überhaupt eine planare Darstellung existiert. In der vorliegenden Arbeit wird ein Algorithmus mit linearer Laufzeit präsentiert der prüft, ob sich ein gegebener Graph planar in der Ebene darstellen lässt.
Inhaltsverzeichnis
1 Planarität von Graphen - Eine Einführung
2 Grundlegende Überlegungen
2.1 Uneindeutigkeit der planaren Darstellung
2.2 Voraussetzungen für den Graphen G
3 Historische Planaritätskriterien
4 Der ’vertex addition’-Algorithmus
4.1 st-Nummerierung
4.1.1 Vorbereitung: Eine modifizierte Tiefensuche
4.1.2 Teilalgorithmus: Path
4.1.3 st-Nummerierung
4.1.4 Laufzeitbetrachtung
4.1.5 Ein kleines Beispiel
4.2 Bush-Form und PQ-Bäume
4.2.1 Die Bush-Form eines Graphen
4.2.2 PQ-Bäume
4.2.3 Wichtiges Lemma
4.2.4 Pattern Matching mit neun Templates
4.3 Der Planaritätstest
5 Beispielhafte Anwendung der ’vertex addition’-Methode
5.1 Erstes Beispiel aus [NR04]
5.2 Der vollständige Graph K5
5.3 Der vollständige bipartite Graph K3,3
5.4 Der fast vollständige bipartite K 3,3
6 Resümee und Ausblick
A Definitionen
Abbildungsverzeichnis
1 Zwei unterschiedliche planare Darstellungsformen desselben Graphen K 5
3 K 3,
4 Graph G mit st-Nummerierung
5 Beispielgraph
6 Ergebnis von Algorithmus 5
7 Initialisierung
8 Kante (c, d)
9 Kante (b, c)
10 Kante (e, c)
11 Kante (f, c)
12 st-Nummerierung c
13 Kante (b, a)
14 Endergebnis der st-Nummerierung
15 Graph G mit st-Nummerierung
16 G 4von G
17 Bush-Form von G t
19 Beispiel eines P-Knoten
20 Beispiel eines Q-Knoten
21 Bush-Form und PQ-Form eines Graphen G. Aus [NR04]
22 Pattern P 1
23 Ersatz von P 1
24 Pattern P 2
25 Ersatz von P 2
26 Pattern P 3
27 Ersatz von P 3
28 Pattern P 4
29 Ersatz von P 4
30 Pattern P 5
31 Ersatz von P 5
32 Pattern P 6
33 Ersatz von P 6
34 Pattern Q 1
35 Ersatz von Q 1
36 Pattern Q2
37 Ersatz von Q2
38 Pattern Q3
39 Ersatz von Q3
40 Beispielgraph mit ST-Nummerierung
41 Bush-Form B 1und PQ-Baum nach Zeile 4
42 Ersatz des (Blatt)Knotens 2
43 Sukzessive Anwendung der Patterns P 3 und P 5 auf Abbildung 42
44 Bush-Form B 3und PQ-Baum nach den ersten Schritten
45 Anwendung von P 3 und Q 3 auf Abbildung 44
46 Bush-Form B 4und PQ-Baum nach Entfernung von 4
47 Anwendung von P 3 und Q 2 auf Abbildung 46
48 Anwendung von P 4 auf 47
49 Bush-Form B 5und PQ-Baum nach Entfernung des (Blatt)Knotens 5
50 Eine Einbettung des planaren Graphen aus Abbildung 40
51 Schematischer Ablauf der ’vertex addition’-Methode für den Graphen K
52 Algorithmus Planar für den Graphen K 3,
53 Algorithmus Planar für den Graphen K 3,3mit einer Kante weniger
1 Planarität von Graphen - Eine Einführung
Als planarer Graph wird derjenige Graph bezeichnet, der sich in der Ebene lässt ohne dass sich zwei Kanten des Graphen schneiden. Die ersten Überlegungen zur Planarität finden sich bereits bei Euler und seinem berühmten Polyedersatz. In den letzten Jahrzehnten, insbesondere durch die Entwicklungen im Bereich der Mikrochips (VLSI), wurde die Frage nach der planaren Darstellung eines Graphen immer . Weitere Anwendungen finden sich in sämtlichen Bereichen in denen Leitungen oder Transportwege (Kanten) zwischen verschiedenen Standorten bzw. Quellen und Senken (Knoten) überschneidungsfrei in einer Ebene gezeichnet bzw. verlegt werden müssen. Zunächst stellt sich allerdings die Frage, ob für einen gegebenen Graphen überhaupt eine planare Darstellung existiert. In der vorliegenden Arbeit wird ein Algorithmus mit linearer Laufzeit präsentiert der prüft, ob sich ein gegebener Graph planar in der Ebene darstellen lässt. Das konkrete Aussehen dieser Darstellung wird durch eine Erweiterung des in dieser Arbeit vorgestellten Algorithmus berechnet. Die konkrete Darstellung Erweiterung, welche in [NR04] erläutert wird, würde allerdings den Rahmen der Arbeit sprengen.
Ausgehend von den ersten Überlegungen von Euler zur Planarität von Graphen stellt sich die historische Entwicklung in diesem Forschungszweig in den letzten 50 Jahren wie folgt dar:
1961 Auslander und Parter [AP61]: Planaritätstests sind polynominial, O (n 3)-Algorithmus 1964 Demoucron, Malgrange und Pertuiset [DMP64]: Einfacher O (n 2)-Algorithmus 1967 Lempel, Even und Cederbaum [LEC67]: O (n 2)-Algorithmus (erste Überlegungen ’vertex addition’-Methode)
1974 Hopcroft und Tarjan [HT74]: Durchbruch mit einem O (n)-Algorithmus. A schwer zu verstehen und noch schwerer zu implementieren.
1976 Even, Tarjan [ET76] und Booth, Lueker [BL76] entwickeln unabhängig Erweiterungen zu [LEC67] und verbessern die ’vertex addition’ Methode zu einem O (n)-Algorithmus. Die dazugehörige planare Einbettung kann durch einen, in der Abhandlung ebenfalls erwähnten, zusätzlichen O (n 2)-Algorithmus gefunden werden.
1985 Chiba, Nishizeki, Abe und Ozawa [CNAO85] publizieren eine Modifikation von [LEC67] welche eine planare Einbettung in O (n) liefert.
1993 Mehlhorn, Mutzel, und Naher [MMN93] entwickeln während ihrer Arbeit an LE- DA1den Algorithmus von [HT74] weiter, so dass, zusätzlich zum Planaritätstest, eine planare Einbettung in O (n) geliefert wird.
1999 Wei-Kuan Shih und Wen-Lian Hsu [WKWL99] entwickeln einen einfachen O (n)- Algorithmus der mit einer neuen Datenstruktur (PC-Bäume) arbeitet und eine planare Einbettung oder die Kuratowski-Teilgraphen liefert.
1999 Boyer und Myrvold [BM99] entwickeln einen ähnlichen Algorithmus wie [WKWL99].
Die eben vorgestellten Algorithmen und Datenstrukturen finden sich in zahlreichen Softwarepaketen wieder. Die in [BL76] erläuterte Datenstruktur wurde in C++ implementiert [Lei97]. Das Softwarepaket Planarity [Boy] implementiert den in [BM99] vorgestellten Algorithmus. Im Softwarepaket Mathematica wird der in [AP61] vorgestellte Algorithmus für Planaritätstests genutzt. Das Open Graph Drawing Framework [GCK] implementiert die in [WKWL99] und [BM99] vorgestellten D und Algorithmen. Eine Implementierung des hier vorgestellten Verfahrens zum Testen der Planarität von Graphen findet sich im Grapheditor JGraphEd [Har] von John Harris.
In dieser Arbeit werden zunächst in Abschnitt 2 grundlegende Überlegungen die die Grundlage für das Verständnis der folgenden Abschnitte liefern. Im A 3 werden zwei der ältesten Planaritätskriterien für Graphen vorgestellt und ein Verweis auf eine Vielzahl anderer Kriterien geliefert. Der Planaritätstest findet sich in Abschnitt 4. Zunächst wird zur Vorbereitung des Planaritätstests eine spezielle N in Abschnitt 4.1 und eine neue Datenstruktur in 4.2 präsentiert. Beides bildet die Grundlage des Planaritätstests der in Abschnitt 4.3 dargestellt wird. Einige Beispiele in 5 verdeutlichen die Arbeitsweise des Planaritätstests aus Abschnitt 4.3. Ein kurzes Resümee und ein Verweis auf neuere Entwicklungen runden die Arbeit ab.
2 Grundlegende Überlegungen
2.1 Uneindeutigkeit der planaren Darstellung
Unter der planaren (bzw. ebenen oder geplätteten) Darstellung eines Graphen G man die Darstellung in der Ebene, so dass sich keine zwei Kanten schneiden, oder anders formuliert: Zwei Kanten treffen sich ausschließlich in den Knoten des Graphen. Hierbei ist offensichtlich, dass für einen gegebenen Graphen G, sofern eine planare D existiert, diese nicht notwendigerweise eindeutig ist. Abbildung 1 zeigt zwei unterschiedliche planare Darstellungsformen desselben Graphen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1
Zwei unterschiedliche planare Darstellungsformen desselben Graphen.
2.2 Voraussetzungen für den Graphen
Es ist offensichtlich, dass die Tatsache, ob der Graph gerichtet oder ungerichtet ist, für die Frage ob es eine planare Darstellung gibt unerheblich ist. Zur Vereinfachung wird im Folgenden von ungerichteten Graphen ausgegangen. Ferner sind nur Knoten von B die mehr als eine ausgehende Kante besitzen. Knoten die nur eine Kante haben können ohne Verletzung der Überschneidungsfreiheit an einen planaren Graphen ängt werden können. In [Har72] wurde gezeigt dass ein beliebiger Graph genau dann planar ist, wenn alle seine zweifach zusammenhängenden Komponenten planar sind. Aufgrund dieser Erkenntnis, und der Tatsache, dass sich die zweifach zusammenhä Komponenten eines Graphen G leicht berechnen lassen, werden im Folgenden ausschließlich zweifach zusammenhängende Graphen betrachtet.
3 Historische Planaritätskriterien
Bevor man sich über die konkrete Darstellung eines planaren Graphen in der Ebene Gedanken machen kann muss die Frage geklärt werden, ob es überhaupt eine planare Darstellung eines Graphen G gibt. Erste hinreichende, und einfach zu prüfende, K um die Planarität eines Graphen auszuschließen, können bereits aus der Eulerschen Polyederformel2abgleitet werden.
- Für jeden planaren Graph G mit v ≥ 3 Knoten folgt
Abbildung in dieser Leseprobe nicht enthalten
Hieraus lässt sich folgern dass der Graph in Abbildung 2 nicht planar ist. 3
- Für jeden bipartiten planaren Graph K s, r gilt
Abbildung in dieser Leseprobe nicht enthalten
Hieraus lässt sich folgern dass der Graph in Abbildung 3 nicht planar ist. 4
In Abbildung 2 und Abbildung 3 sind beispielhaft zwei Graphen dargestellt für die keine planare Darstellung gefunden werden kann. Diese beiden Graphen bilden die Grundlage des Satzes von Kuratowski. Der Satz von Kuratowski [Kur30] ist ein und notwendiges Kriterium für die Planarität eines Graphen. Allerdings sich die Anwendung des Satzes in der Praxis, insbesondere bei größeren Graphen, als sehr zeitaufwändig. Nichts desto trotz soll der Satz, und eine Variante davon, hier kurz als ein Kriterium für die Planarität eines Graphen präsentiert werden.
Abbildung in dieser Leseprobe nicht enthalten
Sat z 2 (Satz von Wagner) . Ein Graph G ist genau dann planar, wenn weder K 5 no c h K 3,3 ein Minor von G sind.
Andere Planaritätskriterien wurden von Whitney [Whi32], MacLane [ML37], F und Rosenstiehl [FR82], Schnyder [Sch89], Harary [Har72] sowie de Verdière [Ver90] entwickelt. All diese Kriterien sind allerdings entweder in den für die Prüfung benötigten Datenstrukturen oder den zu leistenden Vorarbeiten komplexer als die bisher genannten. Auf die Darstellung dieser Kriterien wird daher hier verzichtet.
Es ist offensichtlich, dass allein mit den beiden genannten Kriterien die Prüfung Planaritätseigenschaft nur für sehr kleine Graphen praktikabel ist. Im folgenden Kapitel wird daher nun der so genannte ’vertex addition’-Algorithmus [LEC67], inkl. den Erweiterungen aus [ET76] und [BL76], vorgestellt mit dem die Planarität eines beliebigen Graphen bei linearer Laufzeit entschieden werden kann.
4 Der ’vertex addition’-Algorithmus
4.1 st-Nummerierung
Unter einer st-Nummerierung eines Graphen G mit v Knoten (siehe Abbildung 4) man die Nummerierung der Knoten von 1 bis v, so dass die Knoten 1 und v und jeder Knoten j ∈ V \{1, v } zu den Knoten i und k, mit i < j und j < k, adjazent sind. Der Knoten 1 wird hierbei als Quelle, der Knoten v als Senke bezeichnet. In [ET76] wurde gezeigt, dass jeder zweifach zusammenhängende Graph eine st-Nummerierung besitzt.
Im Folgenden wird zunächst eine modifizierte Tiefensuche vorgestellt, welche im Gegensatz zur normalen Tiefensuche lediglich zwei zusätzliche Werte ermittelt. A ßend wird ein essentielles Teilproblem der st-Nummerierung erläutert und ßend der gesamte Nummerierungsalgorithmus präsentiert. Eine kurze L , schließlich soll die Entscheidung ob der Graph planer ist in linearer Zeit fallen, und ein Beispiel runden den Abschnitt ab.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4
Graph G mit st-Nummerierung
4.1.1 Vorbereitung: Eine modifizierte Tiefensuche
Um die st-Nummerierung eines Graphen G zu berechnen ist zunächst eine leicht modi- fizierte Tiefensuche nötig die für jeden Knoten den Vaterknoten, eine DF-Nummer und eine LOW-Nummer berechnet. Hinter der DF-Nummer verbirgt sich die Reihenfolge in der die Knoten des Graphen bei der Tiefensuche durchlaufen wurden. Die LOW- Nummer eines Knoten ist definiert als
Abbildung in dieser Leseprobe nicht enthalten
Zunächst wird also, ausgehend von einem beliebigen Startknoten, durch T der Baum T aufgebaut. Beim Hinabsteigen werden die DF-Nummern (Zeile 11), vorläufige LOW-Nummern (Zeile 12), sowie Verweise auf die Vaterknoten (Zeile 17) gesetzt.
Beim Hinaufsteigen werden die LOW-Nummern der Knoten korrigiert (Zeile 19 bzw. Zeile 21) und auf ihren endgültigen Wert gesetzt. Der dargestellte Algorithmus, auf den in Abbildung 5 dargestellten Graphen, ergibt den in Abbildung 6 Baum, wobei die Baumkanten durchgehend, die restlichen (Rückwärts)Kanten des Graphen unterbrochen gezeichnet wurden.
4.1.2 Teilalgorithmus: Path
Nachdem die leicht modifizierte Tiefensuche alle für die spätere st-Nummerierung ötigen Daten berechnet hat, soll nun ein essentielles Teilproblem des st-Algorithmus separat vorgestellt werden, um die Darstellung des gesamten, im nächsten Abschnitt folgenden, Algorithmus zu vereinfachen.
Abbildung in dieser Leseprobe nicht enthalten
6Eine Kante des Graphen G die nicht Teil des DFS-Baums ist
Abbildung in dieser Leseprobe nicht enthaltenAbbildung in dieser Leseprobe nicht enthalten
Abbildung 5
Beispielgraph
Abbildung 6
Ergebnis von Algorithmus 5
Zunächst werden die Kante (t, s) eines Graphen G gewählt der bereits durch den im vorherigen Abschnitt vorgestellten Algorithmus bearbeitet wurde. Hierbei gelten für die Knoten t und s die Bedingungen t. DFN = 1 und s. DFN = 2. Die beiden Knoten t und s und die dazugehörige Kante (t, s)werden als ALT markiert, alle anderen Knoten und Kanten als NEU. Der Teilalgorithmus findet, ausgehend von einem Knoten v, einen Pfad zu einem bereits als ALT markierten Knoten w. Hierfür werden vier F benötigt.
Fall 1: Es existiert eine als NEU markierte Rückwärtskante (v, w)
Markiere (v, w) als ALT return v → w
Der einfachste Fall ist also gegeben wenn direkt vom zu untersuchenden Knoten v unverbrauchte, sprich eine als NEU markierte, Kante zu einem als ALT markierten Knoten existiert.
Fall 2: Es existiert eine als NEU markierte Baumkante (v, w) Durch LOW (w) ist ein Pfad von w = w 0 über w 1,..., w k −1 zu dem Knoten w k. DFN = LOW (w) gegeben
Markiere alle Knoten und Kanten auf dem Pfad als ALT return v → w 1 → ... → w k
Beim zweiten Fall wird als zunächst im Baum eine unverbrauchte Kante genutzt um im Baum eine Ebene tiefer hinabzusteigen. Anschließend, hier wird die Bedeutung der LOW − Nummern deutlich, kann über Rückwärtskanten ein als ALT markierter Knoten erreicht werden.
Fall 3: Es existiert eine als NEU markierte Rückwärtskante (w, v) Es gelte hier zusätzlich w. DFN > v. DFN
Sei ein Pfad von w = w 0 über w 1,..., w k −1 zu einem ALT markierten Knoten w k gegeben
(Anm.: Dieser Pfad lässt sich leicht über die Vaterverweise finden.)
Markiere alle Knoten und Kanten auf dem Pfad als ALT return v → w 0 → w 1 → ... → w k
Der dritte Fall ist etwas komplexer. Zur Pfadfindung wird eine Rückwärtskante genutzt die in v endet, um von dort, mit Hilfe der Vaterverweise der Knoten, einen Pfad zu einem als ALT markierten Knoten zu finden. Als letzter Fall bleibt die Abbruchbedingung
Fall 4: Es existiert keine als NEU markierte Kante (v, w) oder (w, v) return ∅
Der Aufruf der Fallunterscheidungen mittels PATH (v) erfolgt hierbei immer mit einem bereits als ALT markierten Knoten als Eingabe. Nachdem die Vorbereitungen sind kann nun der eigentliche Algorithmus zur st-Nummerierung präsentiert werden.
4.1.3 st-Nummerierung
Da die im vorherigen Abschnitt dargestellte Fallunterscheidung PATH (v) einen Groß- teil der Arbeit erledigt ist der restliche Algorithmus für die st-Nummerierung (A 4.1.3) kurz und einfach zu verstehen. Als Eingabe für den Algorithmus wird ein Graph G benötigt der bereits von Algorithmus 4.1.1 bearbeitet wurde. Wie im Abschnitt bereits erwähnt wird initial die Kante (t, s) mit t. DFN = 1 und s. DFN = 2 ausgewählt. Als zusätzliche Datenstruktur benötigt der Algorithmus einen Stack S.
Abbildung in dieser Leseprobe nicht enthalten
Bevor der Algorithmus 4.1.3 an einem Beispiel vorgestellt wird, soll kurz noch ein Blick auf die Laufzeit des Verfahrens (inkl. Algorithmus 4.1.1) erfolgen.
4.1.4 Laufzeitbetrachtung
Durch die ALT/NEU-Markierung wird in Algorithmus 4.1.1 jeder Knoten genau einmal besucht (Zeile 18) und für jeden Knoten wird die Adjazenzliste durchlaufen (Zeile 14), sprich jede Kante wird besucht. Die dadurch implizierte Laufzeit für die Tiefensuche ist O (e + v).
Für den Algorithmus 4.1.3 lässt sich dieselbe Argumentation mit der ALT/NEU- Markierung anführen. Jeder Knoten und jede Kante wird genau einmal besucht. Auch hier erhält man also eine lineare Laufzeit O (e + v). Der Algorithmus zur st-Nummerierung ist also im Hinblick auf die Laufzeit in der Klasse O (n) einzuordnen, sprich linear zur K . Kantenmenge.
4.1.5 Ein kleines Beispiel
Häufig gestellte Fragen
Was ist die Planarität von Graphen?
Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden kann, ohne dass sich zwei seiner Kanten schneiden. Die Kanten dürfen sich nur in den Knoten des Graphen treffen.
Warum ist die Planarität von Graphen wichtig?
Die Planarität von Graphen ist wichtig in Bereichen wie der Entwicklung von Mikrochips (VLSI), wo Verbindungen ohne Überschneidungen realisiert werden müssen, sowie in anderen Anwendungen, in denen Leitungen oder Transportwege zwischen Standorten überschneidungsfrei verlegt werden sollen.
Was sind einige historische Planaritätskriterien?
Einige historische Planaritätskriterien umfassen:
- Auslander und Parter (1961): Polynomieller Algorithmus, O(n^3)
- Demoucron, Malgrange und Pertuiset (1964): Einfacher O(n^2)-Algorithmus
- Lempel, Even und Cederbaum (1967): O(n^2)-Algorithmus (Vorläufer der 'vertex addition'-Methode)
- Hopcroft und Tarjan (1974): O(n)-Algorithmus
- Even, Tarjan (1976) und Booth, Lueker (1976): Verbesserungen der 'vertex addition'-Methode zu einem O(n)-Algorithmus
- Chiba, Nishizeki, Abe und Ozawa (1985): Modifikation, die eine planare Einbettung in O(n) liefert
- Mehlhorn, Mutzel, und Naher (1993): Weiterentwicklung des Algorithmus von Hopcroft und Tarjan
- Wei-Kuan Shih und Wen-Lian Hsu (1999): Einfacher O(n)-Algorithmus mit PC-Bäumen
- Boyer und Myrvold (1999): Ähnlicher Algorithmus wie Shih und Hsu
Was ist der 'vertex addition'-Algorithmus?
Der 'vertex addition'-Algorithmus ist ein Verfahren zum Testen der Planarität eines Graphen. Es handelt sich um eine Methode, die in linearer Zeit prüft, ob ein gegebener Graph planar in der Ebene dargestellt werden kann. Erweiterungen des Algorithmus können das konkrete Aussehen dieser Darstellung berechnen.
Was ist eine st-Nummerierung?
Eine st-Nummerierung eines Graphen G mit v Knoten ist eine Nummerierung der Knoten von 1 bis v, so dass die Knoten 1 und v adjazent sind und jeder Knoten j ∈ V \{1, v} zu den Knoten i und k mit i < j und j < k adjazent ist. Der Knoten 1 wird als Quelle, der Knoten v als Senke bezeichnet.
Was ist die Laufzeit des 'vertex addition'-Algorithmus?
Der 'vertex addition'-Algorithmus, einschließlich der st-Nummerierung, hat eine lineare Laufzeit von O(n), wobei n die Anzahl der Knoten und Kanten des Graphen ist. Dies macht ihn effizient für die Planaritätsprüfung.
Welche Voraussetzungen gelten für den Graphen bei der Planaritätsprüfung?
Zur Vereinfachung wird von ungerichteten Graphen ausgegangen. Ferner sind nur Knoten von Bedeutung die mehr als eine ausgehende Kante besitzen. Knoten die nur eine Kante haben können ohne Verletzung der Überschneidungsfreiheit an einen planaren Graphen gehängt werden. Weiterhin werden ausschließlich zweifach zusammenhängende Graphen betrachtet, da ein beliebiger Graph genau dann planar ist, wenn alle seine zweifach zusammenhängenden Komponenten planar sind.
Was ist der Satz von Kuratowski?
Der Satz von Kuratowski ist ein hinreichendes und notwendiges Kriterium für die Planarität eines Graphen. Er besagt, dass ein Graph genau dann planar ist, wenn er weder den vollständigen Graphen K5 noch den vollständigen bipartiten Graphen K3,3 als Teilgraph enthält, bzw. keine Unterteilung von K5 oder K3,3 enthält.
Was ist der Satz von Wagner?
Der Satz von Wagner besagt, dass ein Graph G genau dann planar ist, wenn weder K5 noch K3,3 ein Minor von G sind.
- Quote paper
- Florian Forster (Author), 2011, Planarität von Graphen - die ’vertex addition’-Methode, Munich, GRIN Verlag, https://www.grin.com/document/213452
