Planarisierung basierend auf: Crossings and Planarization (Mutzel, Jünger, Gutwenger, Buchheim, Ebner `04) An experimental Study of Crossing Minimization

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


PG 478 : OGDF Planarisierung

2

Inhalt

• Einführung

• Planarisierungmethode

• Experimentelle Ergebnisse

• Schlussfolgerung



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



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



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



6


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



7


Ergebnis:

Graph mit max. |Vd| - vielen Überkreuzungen

in jeder planaren Zeichnung

2 Möglichkeiten für jeden Dummy d :

dd



8


- 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



9

PlanarisierungsmethodeBeispiel :

u1

v2

v1

u2

u2

v1

v2

u1



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



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



12

Edge Re-Insertion Problem

1. Einzelne Kanten nacheinander einfügen

a. fixe Einbettung

b. variable Einbettung

2. Nachbearbeitung

3. Permutation



13


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

Kante e kreuzt andere Kante

e benutzt Kante im geometrischen dualen Graphen



14


extended dual graph:

w v



15


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



16


Beispiel:

8

9

6

7

5

31

2

4

8

9

6

7

5

31

2

4



17


2

1

3

9

47

8

56

2-fach Zusammenhangskomponenten(Blöcke)

Cut vertex

3-fach Zusammenhangs-

komponenten

z.B.:



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



19

Qf

SPQR-Bäume

serielle Anordnung

S

Parallele Anordnung

P


R

Kante im Graphen

Q

Skelette:

1

2

34

5a h

b

c

g

fd

e

Qa Qh Qc QgP

R

Qb



20

SPQR-Bäume

serielle Anordnung

S

Parallele Anordnung

P


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



21


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



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



23


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



24


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



25

11

21

1918

20

2


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



26


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



27


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



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



29

Experimentelle ErgebnisseFIX

vs.

VAR



30

Experimentelle ErgebnisseNach-

bearbeitung



31


Permutation



32

Experimentelle ErgebnissePQ1

vs.

PQ100



33

Experimentelle ErgebnisseVergleich:

FIX / VAR

und

NONE / ALL



34


Laufzeit



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



36

Experimentelle ErgebnisseVergleich:



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.



38

Ende



39


Documents

Planarisierung basierend auf: Crossings and Planarization (Mutzel, Jünger, Gutwenger, Buchheim, Ebner `04) An experimental Study of Crossing Minimization