Planarisierung basierend auf: Crossings and Planarization (Mutzel, Jünger, Gutwenger, Buchheim,...

Planarisierung

basierend auf:

• Crossings and Planarization

(Mutzel, Jünger, Gutwenger, Buchheim, Ebner `04)

• An experimental Study of Crossing Minimization Heuristics(Gutwenger, Mutzel `03)

PG – 478: Open Graph Drawing Framework

PG - Vortrag

Referent: Sebastian Sondern

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

2

Inhalt

• Einführung

• Planarisierungmethode

• Experimentelle Ergebnisse

• Schlussfolgerung

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

3

Einführung

• kombinatorische Einbettung

Knoten 1 : < 2 , 5 , 4 >

...

Knoten 5 : < 1 , 2 , 3 , 4 >

Fläche A : < f , e , d , c , g >

...

Fläche D : < b , g , c >

• planarer Graph

• Flächen / faces

1

5

4 3

2

a b

cd

f

e g

A

B

C

D

cd

f

e g4

5

1 2

3

C

DBA

a b

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

4

Einführung

Warum Planarität ?

Lesbarkeit steigt mit weniger Kreuzungen

VLSI - Design

Motivation: zeichne gegebenen Graphen

in der Ebene und minimiere die Anzahl von Kantenkreuzungen

NP-hard

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

5

Planarisierungsmethode

Aufteilung in einzelne Optimierungsprobleme

1. Maximum Planar Subgraph Problem (MPSP)

2. Edge Insertion Problem (EIP)

( Batini, Talamo, Tamassia `84)

6

5

7

4

3

2

1

8

1

2

3 4

6

8

5

7

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

6

Planarisierungsmethode

Aufteilung in einzelne Optimierungsprobleme

1. Maximum Planar Subgraph Problem (MPSP)

2. Edge Insertion Problem (EIP)

( Batini, Talamo, Tamassia `84)

1

2

3 4

6

8

5

7

1

2

3 4

6

8

5

7

9

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

7

Planarisierungsmethode

Ergebnis:

Graph mit max. |Vd| - vielen Überkreuzungen

in jeder planaren Zeichnung

2 Möglichkeiten für jeden Dummy d :

dd

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

8

Planarisierungsmethode

- MPSP und EIP auch einzeln NP-hard

heuristische Lösung

- optimale Lösungen für die jeweiligen Teilprobleme

ergeben zusammen nicht unbedingt die

optimale Lösung für den Graphen

- Aber: in der Praxis gute Ergebnisse

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

9

PlanarisierungsmethodeBeispiel :

u1

v2

v1

u2

u2

v1

v2

u1

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

10

Maximum Planar Subgraph Problem

Branch & Cut - Algorithmus (Jünger & Mutzel `96)- # zu entfernende Kanten < 10 :

• optimale Lösung möglich• schnell zu berechnen

- sonst:zu langsam für praktischen Einsatz

• beginne mit Graphen ohne Kanten• füge Kanten nacheinander hinzu, wenn möglich

(Planaritätstest)

Alternative: berechne maximal planar subgraph

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

11

Maximal Planar Subgraph Problem

besser: PQ-Baum basierter Algo (Jayakumar et al. `89)

• worst-case Laufzeit quadratisch• garantiert keinen maximal planaren Teilgraphen• in der Praxis weit besser• randomisiert und wiederholt (wg.: Wahl der 1. Kante)

- hier: PQ1, PQ10, PQ50, PQ100

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

12

Edge Re-Insertion Problem

1. Einzelne Kanten nacheinander einfügen

a. fixe Einbettung

b. variable Einbettung

2. Nachbearbeitung

3. Permutation

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

13

Edge Re-Insertion Problem

1. Einzelne Kanten nacheinander einfügena. fixe Einbettung gegeben: FIX

Kante e kreuzt andere Kante

e benutzt Kante im geometrischen dualen Graphen

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

14

Edge Re-Insertion Problem

extended dual graph:

w v

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

15

Edge Re-Insertion Problem

1. Einzelne Kanten nacheinander einfügena. fixe Einbettung gegeben: FIX

Kante e kreuzt andere Kante

e benutzt Kante im geometrischen dualen Graphenalso:

kürzesten Weg berechnen

aber:

die Anzahl der Kantenüberkreuzungen

hängt stark von der fixen Einbettung ab

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

16

Edge Re-Insertion Problem

Beispiel:

8

9

6

7

5

31

2

4

8

9

6

7

5

31

2

4

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

17

Edge Re-Insertion Problem

2

1

3

9

47

8

56

2-fach Zusammenhangskomponenten(Blöcke)

Cut vertex

3-fach Zusammenhangs-

komponenten

z.B.:

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

18

SPQR-Bäume

serielle Anordnung

S

Parallele Anordnung

P

3-fach Zshgk (rigid)

R

Kante im Graphen

Q

Skelette:

1

2

34

5a h

b

c

g

fd

e

Qa Qh Qc Qg

R

Qb

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

19

Qf

SPQR-Bäume

serielle Anordnung

S

Parallele Anordnung

P

3-fach Zshgk (rigid)

R

Kante im Graphen

Q

Skelette:

1

2

34

5a h

b

c

g

fd

e

Qa Qh Qc QgP

R

Qb

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

20

SPQR-Bäume

serielle Anordnung

S

Parallele Anordnung

P

3-fach Zshgk (rigid)

R

Kante im Graphen

Q

Skelette:

1

2

34

5a h

b

c

g

fd

e

QdQe

Qf S

Qa Qh Qc QgP

R

Qb

P

S

R

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

21

Edge Re-Insertion Problem

Einfügen einer Kante in eine variable Einbettung VAR

(Gutwenger, Mutzel, Weiskircher `01)

min. Anzahl an Überkreuzungen über alle

möglichen planaren Einbettungen

• Kernstück des Verfahrens:Berechnung eines optimalen Pfades zweier

nicht-adjazenter Knoten in 2-fach Zshgk.

• Anzahl der verschiedenen Einbettungen exponentiell• Einfügen der Kante mit Hilfe des SPQR-Baumes

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

22

Berechnung eines optimalen Pfades

R3

R4

R1 P R2

R5

SPQR-Baum

R1 R2

1

2

10 8 6

3

12 4

5

79

2

4

7

11

21

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

23

Berechnung eines optimalen Pfades

R3

R4

R1 P R2

R5

SPQR-Baum

R1 R2

1

8 6

3

12 4

5

79

2

4

7

11

21

2

10

13

12

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

24

Berechnung eines optimalen Pfades

R3

R4

R1 P R2

R5

SPQR-Baum

R1 R2

1

8 6

3

15

79

2

4

7

11

21

14

10

13

12

4

5

16

17

v

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

25

11

21

1918

20

2

Berechnung eines optimalen Pfades

R3

R4

R1 P R2

R5

SPQR-Baum

R1 R2

1

8 6

3

15

79

14

10

13

12

4

5

16

17

11

21

19 18

20

21

8 6

3

15

79

14

10

13

12

4

5

16

17

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

26

Edge Re-Insertion Problem

2. Nachbearbeitung

Idee:Kann eine Kante später evtl.“besser“ eingefügt werden ?

MOST x% : nach jeder Iteration werden die Kanten ausgewählt,

die an den meisten Überkreuzungen beteiligt sind

Strategien, welche Kanten erneut eingefügt werden:

NONE: keine Nachbearbeitung

INS: die Kanten aus der MPSP-Optimierung

ALL: alle Kanten

MOST x%: x% aller Kanten

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

27

Edge Re-Insertion Problem

3. Permutation

- erneutes Einfügen der aller gelöschten Kanten aus MPSP

- Kantenreihenfolge permutieren

- bestes Ergebnis behalten- hier: PERM1, Anzahl der Wiederholungen

PERM2, PERM10, PERM20

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

28

Experimentelle Ergebnisse

Vorraussetzungen:

- Benchmark: Rome library

11.528 Graphen, 10 bis 100 Knoten

Gelöschte Kanten Laufzeit / sec

PQ1 19 0.002

PQ10 16

PQ50 15

PQ100 15 0.34

Anzahl der gelöschten Kanten bei Graphen mit jeweils

derselben Anzahl von Knoten

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

29

Experimentelle ErgebnisseFIX

vs.

VAR

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

30

Experimentelle ErgebnisseNach-

bearbeitung

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

31

Experimentelle Ergebnisse

Permutation

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

32

Experimentelle ErgebnissePQ1

vs.

PQ100

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

33

Experimentelle ErgebnisseVergleich:

FIX / VAR

und

NONE / ALL

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

34

Experimentelle Ergebnisse

Laufzeit

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

35

Platz Kreuzungen Laufzeit /sec MPSP Einbettung Nachbe. Perm

1 28,56 8,778 PQ100 VAR ALL PERM20

2 28,61 8,563 PQ100 VAR MOST100 PERM20

3 28,66 5,902 PQ100 VAR MOST25 PERM20

4 29,09 4,359 PQ100 VAR MOST100 PERM10

5 29,35 3,060 PQ100 VAR MOST25 PERM10

6 30,01 0,259 PQ100 FIX MOST100 PERM20

7 30,43 0,258 PQ100 FIX ALL PERM20

8 30,62 0,130 PQ100 FIX MOST100 PERM10

9 31,11 0,128 PQ100 FIX ALL PERM10

10 31,64 0,112 PQ100 FIX MOST25 PERM10

11 33,16 0,054 PQ100 FIX MOST100 PERM2

... ... ... ... ... ... ...

18 46,98 0,036 PQ100 FIX NONE PERM1

19 60,32 0,002 PQ1 FIX NONE PERM1

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

36

Experimentelle ErgebnisseVergleich:

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

37

Schlussfolgerung

1. Bei der Nachbearbeitung sollten alle Kanten mit einbezogen werden. Selbst 25% davon verbessern schon das Ergebnis.

2. Randomisierung und Permutation helfen auch, aber nicht so stark wie die Nachbearbeitung.

3. Ein guter planarer Teilgraph verkleinert nicht nur die Anzahl der Kreuzungen, sondern verbessert auch die Laufzeit.

4. Selbst mit Nachbearbeitung bringt eine variable Einbettung noch Verbesserungen.

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

38

Ende

Referent: Sebastian Sondern

PG 478 : OGDF Planarisierung

39

Experimentelle Ergebnisse