Diese Arbeit behandelt einen einfachen Algorithmus
zum Test von Graphen auf Planarität nach Demoucron, Malgrange
und Pertuiset. Die wesentlichen Grundlagen der Graphen-Theorie werden
wiederholt. Insbesondere die Behandlung von planaren Graphen allgemein
und deren Charakteristika erleichtern das Verständnis des Algorithmus.
Test von Graphen auf Planarit¨
at
Tim Weidner
Universit¨
at Ulm
Institut f¨
ur theoretische Informatik
Zusammenfassung
Diese Arbeit behandelt einen einfachen Algorith-
mus zum Test von Graphen auf Planarit¨
at nach Demoucron, Malgrange
und Pertuiset. Die wesentlichen Grundlagen der Graphen-Theorie wer-
den wiederholt. Insbesondere die Behandlung von planaren Graphen all-
gemein und deren Charakteristika erleichtern das Verst¨
andnis des Algo-
rithmus.
1
Einleitung
Viele Probleme lassen sich auf Graphen zur¨
uckf¨
uhren. Auf dieser Ebene sind sie
einfacher zu l¨
osen und man kann testen, ob deren Struktur planar ist. Planar
bedeutet, es existiert eine Einbettung in der Ebene, sodass sich keine Kanten
oder Knoten innerhalb des Graphen ¨
uberschneiden.
1.1
Motivation f¨
ur effiziente Algorithmen
Die Eigenschaft der Planarit¨
at bringt Vorteile bei der Planung von verschiede-
nen Systemen. Die eigentliche Motivation solche Algorithmen zu erforschen, war
und ist eine m¨
oglichst einfache Anordnung von Komponenten mit m¨
oglichst ge-
ringem Aufwand zu finden, sodass deren vordefinierte Verbindungen sich nicht
¨
uberlagern.
1.2
Elektronische Schaltkreise und Leitungssysteme
Besonders bei der effizienten Gestaltung von elektrischen Schaltkreisen haben
Ingenieure mit Hilfe eines Algorithmus zur planaren Einbettung die M¨
oglichkeit
Komponenten dichter anzuordnen und so die Bauh¨
ohe zu verringern. Ebenso ist
es m¨
oglich aufdruckbare Schaltung f¨
ur Leiterplatten zu gestalten.
Aber nicht nur Elektronische sondern jegliche Art von Leitungssystemen, die
in einer Ebene operieren, profitieren von solchen Algorithmen. Die h¨
ausliche Ver-
sorgung mit Gas- oder Wasserleitungen wird ebenfalls ¨
uber eine planare Struktur
angeschlossen, die sorgf¨
altig geplant werden muss. Bei Gasleitungen bringt eine
planare Struktur zus¨
atzliche Sicherheit, bei z.B. einer Explosion. Bei Wasserlei-
tungen ist eine planare Struktur dagegen essentieller, denn eine ebene Struktur
ben¨
otigt weniger Energie um Wasser auf diesem Weg zu transportieren. Ein
noch besseres Beispiel sind Straßen und vor allem Schienen-Netze. Hier ist eine
Planung ohne planare Einbettung zwar theoretisch m¨
oglich aber mit deutlich
h¨
oheren Kosten verbunden.
1.3
Einbettung
Je besser die Einbettungen der genannten Systeme mit Hilfe eines Algorithmus
geplant werden, umso effizienter sind sie und desto mehr Kosten lassen sich ein-
sparen. Aber lassen sich ¨
uberhaupt alle Graphen in ¨
aquivalente planare Graphen
umformen? Und wie kommt man dann zu einer entsprechenden Einbettung in
eine Ebene? Diese Fragen werden in den folgenden Abschnitten gekl¨
art, doch
zun¨
achst gilt es einige Grundlagen der Graphentheorie in Erinnerung zu rufen.
2
Grundlagen
Ein Knoten ist ein Punkt und eine Kante ist eine Verbindungslinie zwischen
zwei Punkten. Diese Punkte k¨
onnen jedoch auch ein und derselbe sein. Zwei
Punkte heißen adjazent wenn sie durch eine Kante verbunden sind. Ein Graph
G = (V, E) ist ein Tupel aus Knoten (vertices) und Kanten (edges). Die Knoten
sind dabei durch Kanten verbunden. Die Anzahl der Knoten wird als
|V | bzw.
die Anzahl der Kanten als
|E| dargestellt. Eine Kante kann durch die Menge ih-
rer Verbindungspunkte dargestellt werden. Beispielsweise seien v und u Knoten
von G, dann ist
{u, v} die Verbindungskante der Knoten. Ein sogennanter Pfad
ist eine Verbindung zwischen zwei Knoten ¨
uber beliebig viele Kanten innerhalb
eines Graphen. Ein spezieller geschlossener Pfad ist ein Kreis, bei dem zudem
keine Kante doppelt verwendet werden darf. Geschlossen bedeutet in diesem
Fall, dass Start- und Endpunkt identisch sind. Ein Graph G heißt verbunden,
wenn es einen Pfad vom Knoten v zum Knoten u in G gibt, wobei v und u belie-
big sind. Isomorph ist ein Graph G(V
1
, E
1
) zu einem Anderen G(V
2
, E
2
) dann,
wenn beide dargestellten Strukturen bedeutungsgleich sind. Das heißt es gibt
eine Abbildung p : V
1
V
2
mit
{u, w} V
1
sowie
{p(u), p(w)} V
2
. Ein pla-
narer Graph besitzt mindestens eine zu ihm isomorphe Struktur, die sich in die
Ebene einbetten l¨
asst. Eine Region ist eine von Kanten eingeschlossene Fl¨
ache in
einer Einbettung des Graphen in der Ebene. Einen Graphen nennt man bipartit,
falls sich die Menge seiner Knoten in disjunktive Teilmengen aufteilen l¨
asst, und
zwar anhand der Verbindungen der einzelnen Knoten. Daraus folgt außerdem,
dass Regionen in einer Einbettung eines bipartiten Graphen immer mindestens 4
einschließende Kanten besitzen. Ein Subgraph ist ein Graph der entsteht, wenn
man bei einem vorhandenen Graphen beliebig viele Kanten und anh¨
angende
Knoten entfernt. Ein Schnittknoten ist ein Knoten, dessen Entfernen aus einem
Graphen die Anzahl der verbundenen Komponenten erh¨
oht. Weitere Bezeich-
nungen f¨
ur Schnittknoten sind auch
"
cut-vertices" oder
"
articulation points".
Ein zweifach verbundener (engl. biconnected) Graph ist ein Graph ohne jegliche
Schnittknoten. Das bedeutet, wenn ein Knoten entfernt wird bleibt der Graph
weiterhin verbunden. Ein Graph heißt gerichtet, falls jede Kante innerhalb des
Graphen einen Vorg¨
anger-Knoten und einen Nachfolger-Knoten definiert. Alle
Kanten in einem gerichteten Graph sind dann ebenfalls gerichtet. Ein solcher
gerichteter Graph heißt außerdem bidirektional, falls jede gerichtete Kante eine
entgegengesetzt gerichtete Kante ¨
uber die gleichen Knoten besitzt.
2.1
Definition von Fragmenten [Koh04]
Sei ein Graph G = (V, E) gegeben mit einem Subgraphen G = (V , E ). Dann
wird ein Fragment als verbundene Komponente S = (V
s
, E
s
) von G definiert,
sodass E
s
=
{u, v} mit {u, v} E\E oder S ist verbundene Komponente von
G\G unter der Bedingung, dass alle Kanten in G noch enthalten sind, die S und
G verbinden w¨urden. Ein anschauliches Beispiel erleichtert das Verst¨andnis.
Zun¨
achst ist auf der linken Seite ein beliebiger Graph G dargestellt. In der
Abbildung 1.
G
Abbildung 2.
G
Abbildung 3.
Fragmente
Mitte sieht man einen beliebig gew¨
ahlten Subgraphen G' von G. Die farblich
hervorgehobenen Kanten im Graphen auf der rechten Seiten bilden nun jeweils
ein Fragment S von G unter Beachtung von G . Ein Knoten in Fragment S ist
ein Kontaktknoten, wenn sich durch ihn S mit G verbinden l¨
asst. Demnach hat
jedes der 3 Fragmente genau 2 Kontaktknoten mit G .
3
Charakterisierung von planaren Graphen
Ein Graph aus Knoten und Kanten ist nur genau dann planar, wenn er in eine
Sph¨
are eingebettet werden kann. Dies ist beweisbar mit Hilfe von Stereographi-
scher Projektion auf eine Ebene. Hierbei wird der Punkt an dem die Sph¨
are auf
der Ebene aufliegt, mit dem Punkt X auf der Gegenseite verbunden. Von die-
sem Punkt aus projeziert man nun jeden Knoten des Graphen, der in die Sph¨
are
eingebettet wurde auf die Ebene. Diese Methode funktioniert auch umgekehrt,
wenn der Graph zun¨
achst in eine Ebene eingebettet ist. Daraus resultiert, dass
eine Einbettung des planaren Graphen die Ebene in Regionen einteilt. Ebenfalls
folgt aus der Methode der Stereographischen Projektion, dass der Graph immer
Abbildung 4.
Stereographische Projektion
so umgeformt werden kann, damit eine bestimmte Region die ¨
Außere ist und
den Graphen umschließt. Ein planarer Graph heißt maximal, wenn keine Kante
mehr eingef¨
ugt werden kann, sodass er noch planar ist. In diesem Fall hat jede
Region genau 3 Kanten und 3 benachbarte Regionen.
3.1
Eulersche Formel
In der Einbettung eines planaren Graphen gibt es ein bestimmtes Verh¨
altnis
der Knoten, Kanten und Regionen. Die Formel, die dieses Verh¨
altnis beschreibt,
lautet: F =
|E| - |V | + 2 Wobei F f¨ur Regionen steht (engl. faces) [Gib85].
3.2
Folgerung aus der Eulerschen Formel f¨
ur
K
5
und
K
3,3
Graphen
Die Formel hilft beim Gegenbeweis zur Planarit¨
at der beiden wichtigsten Gra-
phen f¨
ur den n¨
achsten Satz. Zun¨
achst jedoch m¨
ussen noch einige, leicht herleit-
bare Einschr¨
ankungen getroffen werden.
Graphen mit weniger oder genau 3 Knoten sind immer planar. Eine Region
hat immer mindestens 3 umschließende Kanten und somit in einem maximalen
Graphen auch genau 3 benachbarte Regionen. Um nun eine Beschreibung f¨
ur
das Verh¨
altnis von Regionen und Kanten zu geben, z¨
ahlt man alle Kanten f¨
ur
jede Region in einem maximalen planaren Graphen zusammen und erh¨
alt so
3
· |F | = 2 · |E| |F | =
2
3
· |E|, da jede Kante dann zweifach gez¨ahlt wird.
Daraus ergibt sich nun in Kombination mit der Formel von Euler folgende neue
Formel f¨
ur alle planaren Graphen, wenn man die Regionen durch die vorherige
Formel ersetzt: [Gou88]
F¨
ur G mit
|E| 3 gilt:
|E| - |V | + 2
2
3
· |E| 3 · |E| - 3 · |V | + 6 2 · |E| |E| 3 · |V | - 6
Abbildung 5.
K
5
Abbildung 6.
K
3,3
Der sogenannte Graph K
5
(Abb. 5) erf¨
ullt diese Formel nicht und ist somit
nicht planar.
F¨
ur K
5
gilt: 10
3 · 5 - 6
Der Graph K
3,3
(Abb. 6) erf¨
ullt diese Formel allerdings. Da er jedoch bipartit
ist, hat jede seiner Regionen genau 4 umschließende Kanten. Die Formel ¨
andert
sich in diesem Fall zu:
|E| - |V | + 2
2
4
· |E| 4 · |E| - 4 · |V | + 8 2 · |E| |E| 2 · |V | - 4
F¨
ur K
3,3
gilt mit der neuen Formel: 9
2 · 6 - 4
Somit ist K
3,3
ebenfalls nicht planar.
Theorem 1 (Satz von Kuratowski).
Der Satz von Kuratowski besagt, dass
ein Graph nur dann planar sein kann, wenn er weder K
5
noch K
3,3
als Minoren
enth¨
alt. Ein Graph darf damit weder durch L¨
oschen von Knoten oder Kanten,
noch Zusammenf¨
uhren von adjazenten Knoten, auf einen K
5
oder K
3,3
Graphen
zur¨
uck zu f¨
uhren sein. Aus dem Satz von Kuratowski folgt direkt, dass die Gra-
phen K
5
und K
3,3
die kleinsten, nicht-planaren Subgraphen darstellen. [Gib85]
4
Algorithmus
Die vorangegangenen S¨
atze bieten zwar eine M¨
oglichkeit einen nicht-planaren
Graphen zu erkennen, aber es ist nicht m¨
oglich daraus einen effizienten Algo-
rithmus zur planaren Einbettung zu entwerfen. Einen alternativen Ansatz stellt
der nun folgende Algorithmus dar. Er basiert auf einer iterativen L¨
osung. Falls
m¨
oglich liefert er gleichzeitig eine planare Einbettung in der Ebene. Der Algo-
rithmus funktioniert nach einem Prinzip, welches Demoucron, Malgrange und
Pertuiset im Jahr 1964 ver¨
offentlichten. [DMP64]
4.1
Vorbereitung [Koh04]
Zun¨
achst werden einige Vorraussetzungen geschaffen, n¨
amlich s¨
amtliche Eigen-
schaften eines Graphen, die keinen Einfluss auf die Planarit¨
atskriterien haben
ausgeschlossen. Ab diesem Punkt wird immer von verbundenen Graphen aus-
gegangen, denn falls ein Graph nicht verbunden sein sollte, betrachtet man alle
verbundenen Teilgraphen separat und gef¨
ahrdet dadurch die Planarit¨
at des ur-
spr¨
unglichen Graphen nicht. Dies gilt, da die Teilgraphen sich unabh¨
angig von-
einander in die Ebene einbetten lassen. Ebenso verf¨
ahrt man wenn sich ein Graph
aufgrund von Schnittknoten trennen l¨
asst. Die Teilgraphen verbindet man nach
der Einbettung erneut. Aufgrund dieser Vorraussetzungen haben alle Fragmente
mindestens 2 Kontaktknoten. F¨
ur den Fall, dass ein Graph Mehrfach-Kanten
besitzt, also beliebig viele Kanten, die dieselben Knoten verbinden, werden diese
zu einer Kante zusammengefasst. S¨
amtliche Kanten, die einen Knoten mit sich
selbst verbinden, werden entfernt. Auch Knoten vom Grad 2, sowie ihre Kanten
werden entfernt und durch eine Kante ersetzt.
Als Erstes werden ein Graph G, sowie ein Subgraph G ben¨
otigt, um die Pla-
narit¨
at von G zu testen. Außerdem definiert man ein Fragment S von G unter
Beachtung von G . F¨
ur den Algorithmus muss man zun¨
achst eine spezielle Art
der Regionen definieren. Eine sogenannte zul¨
assige Region R von G enth¨
alt
alle Kontaktpunkte des gegebenen Fragments S. Die Menge aller zul¨
assigen Re-
gionen von S wird definiert als F (S). Zuletzt ben¨
otigt man noch eine spezielle
Definition eines Pfades in S bei dem die Endpunkte jeweils Kontaktpunkte von
S sind. Diesen Pfad nennt man nun -Pfad. Zwei Fragmente S und T definiert
man als konkurrierend, falls erstens gilt:
F (S) F (T ) =
und zweitens, dass f¨
ur jede zul¨
assige Region R
F (S) F (T ) gilt:
A F (S) und B F (T ) welche nicht beide gleichzeitig planar in eine Region
eingebettet werden k¨
onnen.
4.2
Algorithmus zur Entwicklung einer planaren Einbettung eines
Graphen G [Koh04]
Schritt 1
Als erstes sucht man einen Kreis in G als G . Anschließend bettet
man ihn in die Ebene ein. Ein Kreis ist offensichtlich planar.
Schnitt 2
Berechne alle Regionen von G .
Schritt 3
Berechne alle Fragmente S von G unter Beachtung des derzeitigen
Graphen G als M .
Schritt 4
Falls M =
, dann ist G' isomorph zu G und gleichzeitig eine planare
Einbettung von G.
Der Algorithmus terminiert in diesem Fall.
Schritt 5
Berechne alle zul¨
assigen Regionen f¨
ur jedes Fragment S
M als
F (S).
Schritt 6
Falls es ein Fragment S
M mit F (S) = gibt, hat der Graph keine
planare Einbettung und kann somit auch nicht planar sein.
Der Algorithmus terminiert in diesem Fall.
Schritt 7
Falls es ein Fragment S
M mit |F (S)| = 1 gibt, w¨ahle jenes
Fragment S. Gehe zu Schritt 9.
Schritt 8
W¨
ahle ein Fragment S
M mit |F (S)| = 2
Schritt 9
W¨
ahle einen -Pfad aus S und bette ihn in eine Region R
F (S)
ein. Gehe zu Schritt 2.
4.3
Korrektheit des Algorithmus [Koh04]
Die Korrektheit des Algorithmus wird im folgenden bewiesen.
Lemma 1.
Falls zwei konkurrierende Fragmente S und T existieren, f¨
ur die
gilt:
|F (S)| 2 und |F (T )| 2, dann ist F (T ) = F (S) und |F (T )| = 2.
Beweis. Man nehme an, dass F (S) = F (T ). Dann gibt es mindestens 3 unter-
schiedliche Regionen f , g und h. Außerdem sei dann f
F (S) und g F (T ).
Da die Regionen zus¨
atzlich konkurrieren gilt: h
F (S) F (T ).
Nun ist jeder -Pfad L aus S einbettbar in f und jeder -Pfad I aus T einbett-
bar in g.
Daraus folgt, dass jedes -Pfade-Paar (L, I) außerhalb von h einbettbar ist,
aber auch innerhalb. Dies ist jedoch ein Widerspruch zur Definition von kon-
kurrierenden Fragmenten. Daher ist F (S) = F (T ). Um nun zu zeigen, dass es
nur genau 2 zul¨
assige Fl¨
achen gibt, wiederholt man den Beweis mit 3 Regionen
{f, g, h} F (S).
F¨
ur den Beweis einer iterativen L¨
osung definiert man zun¨
achst eine partielle Ein-
bettung G des Subgraphen G von G, wobei G immer neu durch das Entfernen
von Kanten und Knoten vom urspr¨
unglichen G entsteht. Damit ist gew¨
ahrleistet,
dass man die partielle Einbettung zur Einbettung des vollst¨
andigen Graphen G
erweitern kann. Weiterhin definiert man einen neuen Graphen S(G ). Er enth¨
alt
Knoten, welche die Fragmente repr¨
asentieren, sowie Kanten, falls zwei Fragmen-
te konkurrieren.
Lemma 2.
Falls es eine Einbettung G von G gibt und falls F (S)
2 f¨ur alle
Fragmente, dann ist S(G') bipartit.
Beweis. Sei S(G ) nicht bipartit. Dann gibt es einen Kreis ungerader L¨
ange
r 3 mit der Folge: S
1
- S
2
- S
3
- ... - S
i
- S
1
von Knoten in S(G') und
damit von konkurrierenden Fragmenten. Dank Lemma 2 gilt außerdem: F (S
n
) =
F (S
n+1
) und es gibt zwei zul¨
assige Regionen F
1
und F
2
. Um nun die Pfade L
i
aus S
i
gleichzeitig in die vorhandene partielle Einbettung G einzuf¨
ugen und die
Planarit¨
at zu erhalten, muss man sie abwechselnd anhand von i entweder in F
1
oder F
2
einbetten. Da r allerdings ungerade ist f¨
uhrt diese Vorgehensweise zum
Widerspruch beim letzten Schritt, denn i ist ebenfalls ungerade bei S
i
- S
1
.
Theorem 2.
Falls G gerade ist, produziert jede Iteration eine partielle Einbet-
tung.
Beweis. Man zeigt dies durch Induktion ¨
uber n als Anzahl der Iterationen.
n = 1: G ist die Einbettung eines Kreises und Subgraphs von G.
Zu Beginn der Iteration im Algorithmus gibt es f¨
ur jedes Fragment zul¨
assige
Regionen, denn diese sind alle in Abh¨
angigkeit von G' entstanden. Widmet man
sich nun den Schritten 7 und 8 k¨
onnen zwei F¨
alle auftreten.
Fall 1: Es gibt ein Fragment S mit nur einer zul¨
assigen Region. Dann produziert
der Algorithmus eine Einbettung G
L mit -Pfad L aus S, die weiterhin planar
ist.
Fall 2: Alle Fragmente haben zwei zul¨
assige Regionen. In diesem Fall bettet
man den -Pfad L aus S in eine zuf¨
allig gew¨
ahlte zul¨
assige Region ein. Mit
dieser Methode wird mit der Wahrscheinlichkeit
1
2
die andere zul¨
assige Region
gew¨
ahlt. Falls die
"
richtige" Region gew¨
ahlt wurde beh¨
alt man die Einbettung
bei und erh¨
alt so die Planarit¨
at aufrecht. Wenn nun konkurrierende Fragmente
zu S vorhanden sind, muss man S den Fragmenten-Graphen S(G ) zur Hilfe
nehmen. Dank Lemma 2 gilt: Es gibt in diesem Fall 2 zul¨
assige Fl¨
achen f und
g f¨ur alle Fragmente in F (S). Außerdem gilt dann, Fragmente eingebettet in
f konkurrieren nicht mit Fragmenten eingebettet in g. Wenn man also f und
g vertauscht, entsteht eine neue planare Einbettung f¨ur G, die wieder auf G
zur¨
uckgef¨
uhrt werden kann.
Corollary 1.
Der Algorithmus ist korrekt.
1. Falls G planar ist, berechnet der Algorithmus eine planare Einbettung daf¨
ur.
2. Falls der Algorithmus vorzeitig terminiert, weil ein Fragment keine zul¨
assige
Region hat, ist G nicht planar.
Beweis. Dies folgt aus dem Theorem.
Komplexit¨
at
Die Laufzeit des Algorithmus l¨
asst sich durch O(
|V |
2
) absch¨
atzen.
[Mar10]
5
Datenstrukturen f¨
ur planare Graphen
Nachdem man einen Algorithmus zur planaren Einbettung eines Graphen ent-
wickelt hat, m¨
ochte man ihn nat¨
urlich auch gerne praktisch anwenden. Dies ist
nur m¨
oglich, wenn man daf¨
ur eine entsprechend geeignete Datenstruktur w¨
ahlt.
Um einen einfachen Graphen in einer Datenstruktur abzuspeichern eignen sich
verkettete Adjazenz-Listen gut [Gib85]. Hierbei werden Kanten zwischen Kno-
ten ¨
uber die Verkn¨
upfung in einer Liste dargestellt. Der Inhalt der Liste sind
dann die Indizes einzelner Knoten. Wenn jede Kante einmal als Verkn¨
upfung
auftaucht entsteht eine effektive Repr¨
asentation des Graphen, die einfach durch-
sucht werden kann. Allerdings ber¨
ucksichtigt diese Struktur die Besonderheiten
eines planaren Graphen nicht.
F¨
ur die Implementierung eines planaren Graphen verwendet man den Ansatz
einer bidirektionalen Repr¨
asentation [Zie04]. Dabei wird jede Kante in zwei ent-
gegengesetzte gerichtete Kanten geteilt. Diese Struktur speichert f¨
ur jeden Kno-
ten eine zirkul¨
are Adjazenz-Liste aller ausgehenden Kanten, durch die sich die
vorherige und die nachfolgende Kante bestimmen lassen. Zus¨
atzlich muss jede
Kante ihre Gegenkante kennen.
In Abb. 7 werden die Kanten, die mit ihren Nachfolgern eine Region einschließen,
Abbildung 7.
Skizzierte bidirektionale Datenstruktur
als disjunktive Teilmengen der Menge M aller Kanten betrachtet. Jede Kante
l¨
asst sich einer der 4 entstehenden Regionen zuordnen. Um neue Kanten hinzu-
zuf¨
ugen erweitert man einfach die jeweiligen Adjazenz-Listen.
Diese Datenstruktur ist nur die unterste Schicht der Speicherung. Sie bietet
keine geometrische Darstellung, die f¨
ur eventuelle Algorithmen notwendig ist.
Eine geometrische, f¨
ur Menschen lesbare Repr¨
asentation der Daten kann jedoch
hierauf aufbauend implementiert werden.
6
Zusammenfassung
Das Testen bei kleinen Graphen auf Planarit¨
at von Hand folgt relativ einfa-
chen Gesetzen. Die anf¨
anglichen Algorithmen wie der hier Pr¨
asentierte stellen
zwar einen einfachen Zugang zur Thematik her, sind in ihrer Komplexit¨
at je-
doch weit hinter den aktuellen Algorithmen zur¨
uck. Gl¨
ucklicherweise wurden im
Laufe der Zeit weitere Algorithmen f¨
ur dieselbe Problemstellung entwickelt, die
es erm¨
oglichen einen planaren Graphen in linearer Zeit zu testen und einzubet-
ten. Der nach Boyer und Myrvold benannte Algorithmus aus dem Jahr 2004
[BM04] f¨
allt in diese Kategorie. Er liefert zus¨
atzlich, falls m¨
oglich, eine planare
Einbettung.
Literatur
[BM04]
J. Boyer and W. Myrvold. On the Cutting Edge: Simplified O(n) Planarity
by Edge Addition.
Journal of Graph Algorithms and Applications, pages
8(3):241273, 2004.
[DMP64] G. Demoucron, Y. Malgrange, and R. Pertuiset. Graphes planaires: recon-
naissance et construction de representations planaires topologiques.
Rev.
Francaise Recherche Operationnelle, pages 8:3347, 1964.
[Gib85]
A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985.
[Gou88] R. Gould. Graph Theory. http://www.mathcs.emory.edu/~rg/book/chap6.
pdf
, 1988.
[Koh04] A. Kohnert. Algorithm of Demoucron, Malgrange, Pertuiset. http://www.
mathe2.uni-bayreuth.de/EWS/demoucron.pdf
, 2004.
[Mar10] L. Martinet. Drawing Planar Graphs. http://perso.ens-lyon.fr/eric.
thierry/Graphes2010/lucie-martinet.pdf
, 2010.
[Zie04]
J. Ziegler. LEDA Tutorium - Planar eingebettete Graphen, Maps und Faces.
http://www.leda-tutorial.org/de/offiziell/ch05s02s06.html
, 2004.
Häufig gestellte Fragen
Was ist der Inhalt dieser Arbeit über "Test von Graphen auf Planarit¨at"?
Diese Arbeit behandelt einen einfachen Algorithmus zum Test von Graphen auf Planarit¨at nach Demoucron, Malgrange und Pertuiset. Sie wiederholt die wesentlichen Grundlagen der Graphentheorie und behandelt insbesondere planare Graphen allgemein und deren Charakteristika, um das Verst¨andnis des Algorithmus zu erleichtern.
Warum sind effiziente Algorithmen zur Planarit¨at wichtig?
Die Eigenschaft der Planarit¨at bringt Vorteile bei der Planung von verschiedenen Systemen. Die Motivation zur Erforschung solcher Algorithmen war und ist eine m¨oglichst einfache Anordnung von Komponenten mit m¨oglichst geringem Aufwand zu finden, sodass deren vordefinierte Verbindungen sich nicht ¨uberlagern.
Welche Anwendungen profitieren von planaren Einbettungen?
Planare Einbettungen sind besonders relevant bei der Gestaltung elektronischer Schaltkreise, Leitungssysteme (Gas, Wasser), Straßen und Schienennetze. Effiziente Algorithmen zur planaren Einbettung erm¨oglichen dichtere Anordnungen und Kostenersparnisse.
Was sind die Grundlagen der Graphentheorie, die in dieser Arbeit behandelt werden?
Die Arbeit behandelt Definitionen wie Knoten, Kanten, Adjazenz, Graphen (G=(V,E)), Pfade, Kreise, verbundene Graphen, Isomorphie, planare Graphen, Regionen, bipartite Graphen, Subgraphen, Schnittknoten und zweifach verbundene Graphen.
Wie definiert die Arbeit Fragmente?
Ein Fragment wird als verbundene Komponente S=(Vs, Es) eines Subgraphen G' von G definiert, sodass Es = {u, v} mit {u, v} ∈ E\E' oder S ist verbundene Komponente von G\G' unter der Bedingung, dass alle Kanten in G noch enthalten sind, die S und G' verbinden w¨urden.
Was ist das Theorem von Kuratowski?
Der Satz von Kuratowski besagt, dass ein Graph nur dann planar sein kann, wenn er weder K5 noch K3,3 als Minoren enth¨alt. Ein Graph darf damit weder durch L¨oschen von Knoten oder Kanten, noch Zusammenf¨uhren von adjazenten Knoten, auf einen K5 oder K3,3 Graphen zur¨uck zu f¨uhren sein.
Wie funktioniert der Algorithmus zur Entwicklung einer planaren Einbettung?
Der Algorithmus ist iterativ und beginnt mit einem Kreis als Subgraphen G'. Anschließend werden Regionen und Fragmente berechnet. Der Algorithmus sucht dann nach Fragmenten mit zul¨assigen Regionen und bettet diese ein, bis der gesamte Graph eingebettet ist oder festgestellt wird, dass keine planare Einbettung m¨oglich ist.
Welche Datenstrukturen eignen sich f¨ur planare Graphen?
Verkettete Adjazenz-Listen eignen sich f¨ur einfache Graphen. F¨ur planare Graphen wird der Ansatz einer bidirektionalen Repr¨asentation verwendet. Dabei wird jede Kante in zwei entgegengesetzte gerichtete Kanten geteilt. Diese Struktur speichert f¨ur jeden Knoten eine zirkul¨are Adjazenz-Liste aller ausgehenden Kanten.
Welche Schlussfolgerungen zieht die Arbeit?
Die Arbeit kommt zu dem Schluss, dass der hier pr¨asentierte Algorithmus zwar einen einfachen Zugang zur Thematik bietet, jedoch in seiner Komplexit¨at hinter aktuellen Algorithmen zur¨uckliegt. Es werden jedoch weitere Algorithmen f¨ur dieselbe Problemstellung mit linearer Laufzeit genannt.
Ende der Leseprobe aus 10 Seiten
- nach oben
- Arbeit zitieren
- Tim Weidner (Autor:in), 2013, Test von Graphen auf Planarität, München, GRIN Verlag, https://www.hausarbeiten.de/document/230709
Blick ins Buch
