Upload
walburg-radwanski
View
113
Download
3
Embed Size (px)
Citation preview
PG478 1
Planarisierung von
Cluster Graphen
Bihui Dai
PG478 2
Übersicht
Struktur eines Clustergraphs
Motivation
Zeichnung eines Clustergraphs
Planarisierungsalgorithmus
PG478 3
Struktur eines Clustergraphs
PG478 4
RootRootRootRoot
EE FF
EE FF
AA
CC
BB
DD
22
11 33
9988
7766
55
44
12121111
1010AA CC BB DD
2211 33 44 5566 77 88 99 1010 1111 1212
Ein ClusterGraph C(G, T) ein Inklusionsbaum
Sub-Cluster V(E)Sub-Cluster V(E)
ein zugrundliegende ein zugrundliegende GraphGraph
Der von V(E ) induzierte Teilgraph G(E)
1313
1313
PG478 5
Motivation Viele Anwendungen erfordern das Zeichnen von Clustergraphen.
Zum Beispiel:
Netzwerke : lokale Netzwerke und Router in autonomen Systemen, autonome Systeme als Cluster
Informationssysteme: Entity-Relationship Schema, anhand ähnlicher Eigenschaften in Cluster verpacken
PG478 6
Zeichnung eines Clustergraphs
PG478 7
Der Clustergraph C = ( G,T ) wird gezeichnet
Punkte als KnotenPunkte als Knoten
Kurven als KantenKurven als Kanten
Regionen als ClusterRegionen als Cluster
Zeichnung
PG478 8
c-planarer Clustergraph
Hat es in der Zeichnung keine diese Situationen, dann ist der Clustergraph c-planar
1.1. KantekreuzungKantekreuzung
2. Die Kanten 2. Die Kanten überqueren die überqueren die Regionsgrenze Regionsgrenze mehr als einmalmehr als einmal
PG478 9
Zusammenhängender Clustergraph
Der Zusammenhang spielt auch eine bedeutende Rolle in unserem
Planarisierungsalgorithmus:
In dem Planarisierungsalgorithmus ist gegeben für nicht c-planarer zusammenhängender Clustergraph.
Ein clustergraph ist cluster-zusammenhängend , wenn für jeden Knoten von T, G() zusammenhängend ist.
RootRoot
EE FF
AA
CC
BB
DD
22
11 33
9988
7766
55
44
12121111
1010
Zusammenhängender Clustergraph
Nicht zusammenhängender Clustergraph
PG478 10
Planarisierung
Sei ein nicht planarer Graph G = (V, E) gegeben, dann ist eine Planarisierung von G ein eingebetteter planarer Graph G = (V, E), mit:
V = VD; D sind unechte Knoten, jeder repräsentiert eine Kreuzung zwischen zwei Kanten;
Ein Kanten-Pfad von G ist ein Pfad mit Knoten u,d1,…,dk,v; (u ,v) ist eine Kante von E und di sind unechte Knoten.
PG478 11
Sei ein nicht c-planarer Clustergraph C =(G, T) gegeben, dann ist eine Planarisierung von C ein c-planarer Clustergraph C =(G, T), mit:
G ist eine Planarisierung von G;
T ist ein Baum abgeleitet aus T, wobei ein Blatt für jeden unechten Knoten von G hinzugefügt wird.
PG478 12
Planarisierungsalgorithmus
PG478 13
Ablauf: Planarisierungsalgorithmus hat zwei Schritte 1. Maximal-cPlanar 1.1 Spannbaum 1.2 SimpleReinsertion 2. Wiedereinfügung
Problem: Gegebenein zusammenhängender nicht c-planar Clustergraph,
Wie realisiert man diese Planarisierung?
Lösung: Der Planarisierungsalgorithmus wird eingeführt.
PG478 14
Maximal-cPlanar
In Maximal-cPlanar wird ein maximaler c-planarer Subgraph des gegeben Clustergraph berechnet.
Idee: Anfang mit einem "einfachen" zusammenhängenden c-planaren
Subgraph
PG478 15
Die Berechnung besteht aus zwei Schritten:
1. Spannbaum Ein Subgraph wird berechnet, so dass sein zugrundeliegender Graph ein Spannbaum von G ist.
2. SimpleReinsertion Der maximale c-planare Subgraph wird berechnet dadurch, dass die Kanten, die die c-Planarität nicht verletzen, in Spannbaum eingefügt werden.
PG478 16
Spannbaum Nun konstruieren wir den Spannbaum von Cluster:
vv
V V 11
V V 22
V V 33
v2v2
v1v1
v3v3
F(V1)
F(V2 )
F(V3 )
F(V)
ST(V)
PG478 17
SimpleReinsertion
Idee:
Einfügen einiger Kanten in schon konstruiertem Cluster-Spannbaum,
die keine Kreuzungen verursachen können.
PG478 18
wir führen jetzt SimpleReinsertion aus:
Durchlaufe T von unten nach oben Überprüft für jeden Cluster v
Füge eine Kante aus G(v)-ST(v) hinzu Dabei kann keine Kreuzung entstehen
Danach:
Für jede noch nicht eingefügte Kante e Überprüfe c-Planarität wenn Kante e eingefügt wird Füge Kante e ein, falls planar
PG478 19
Wiedereinfügen der verworfenen Kanten
Mit Cmp = ( Gmp, T) von C =( G, T) bezeichnen wir einen maximal c-planaren zusammenhängenden eingebetteten Sub-ClusterGraph.
Problem: Kanteneinfügen, wobei Cluster nicht c-planar bleiben
Die Kanten überqueren mehr als einmal die Regiongrenze
PG478 20
Lösungsidee: (Schritt für Schritt)
-- Es wird ein planarer eingebetteter dualer Graph G‘mp von Gmp
konstruiert.
--Der kürzeste Weg in G‘mp wird berechnet.
--Die Restkanten werden wiedereingefügt .
PG478 21
Die Konstruktion der dualer Graph G‘mp von Gmp
Wir materialisieren die Grenze der Cluster
Die Kante überquert Die Kante überquert die Regiongrenzedie Regiongrenze
Einfügen des Einfügen des kreuzungsknoten v1kreuzungsknoten v1
v1
v2
Einfügen der Einfügen der GrenzkanteGrenzkante
PG478 22
Die Berechnung des kürzeste Weg
Die Ausrichtung und das Entfernen der Kanten von G‘mp .
u v
AA
BB
C
D E
AA
uu
BB
DD
EE
CC
vv
PG478 23
Ende von Planarisierungsalgorithmus
die Komplexität des ganzen Planarisierungsalgorithmus .
Gegeben: n..... die Anzahl der Knoten von Gm..... die Anzahl der Kante von G c.......die Anzahl der Clustern von T........die Anzahl der unechten Knoten
DannDer Algorithmus Maximal-cPlanar benötigt O(mn²);
Der Algorithmus Wiedereinfügung benötigt O( m + m²c).
Insgesamt: Der Planarisierungsalgorithmus berechnet eine Planarisierung von C in O( m + m²c + mn²).
PG478 24
Vielen Dank für Ihre Aufmerksamkeit