24
PG478 1 Planarisierung von Cluster Graphen Bihui Dai

PG4781 Planarisierung von Cluster Graphen Bihui Dai

Embed Size (px)

Citation preview

Page 1: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 1

Planarisierung von

Cluster Graphen

Bihui Dai

Page 2: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 2

Übersicht

Struktur eines Clustergraphs

Motivation

Zeichnung eines Clustergraphs

Planarisierungsalgorithmus

Page 3: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 3

Struktur eines Clustergraphs

Page 4: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 5: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 6: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 6

Zeichnung eines Clustergraphs

Page 7: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 8: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 9: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 10: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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.

Page 11: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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.

Page 12: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 12

Planarisierungsalgorithmus

Page 13: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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.

Page 14: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 15: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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.

Page 16: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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)

Page 17: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 17

SimpleReinsertion

Idee:

Einfügen einiger Kanten in schon konstruiertem Cluster-Spannbaum,

die keine Kreuzungen verursachen können.

Page 18: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 19: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 20: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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 .

Page 21: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 22: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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

Page 23: PG4781 Planarisierung von Cluster Graphen Bihui Dai

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²).

Page 24: PG4781 Planarisierung von Cluster Graphen Bihui Dai

PG478 24

Vielen Dank für Ihre Aufmerksamkeit