Embed Size (px)
Citation preview
B.Goetze, GFaI BerlinStralsund, 25.7.2003
C
A
S
Planarisierung von Graphen und Netzwerken
Überblick
Zur Historie
VinetS-Aktivitäten zur Planarität
Topologische Einbettung
DMP für Graphen
DMP für Netzwerke
Zur Historie Euler: Polyedergleichung Kuratowski: Charakterisierung planarer
Graphen, 1930 Tutte: Barycenter-Algorithmus, 1960 Demoucron, Malgrange, Pertuiset:
Planaritätstest, « DMP-Algorithmus », 1964 Hopcroft, Tarjan: Planaritätstest in O(n), 1974 G. Kant: Geometrische Einbettung im Gitter,
O(n), 1996 Boyer, Myrvold: Planare Einbettung in O(n),
2001
VinetS-Aktivitäten zur Planarität Einarbeitung in Hopcroft-Tarjan
(Stralsund) Diplomarbeit zum Algorithmus von Boyer-
Myrvold (Törsel) Diplomarbeit zum DMP-Algorithmus
(Haak) Implementierung des Algorithmus von
Kant (Haak) Implementierung von DMP und Tutte in
C++ (Goetze) Problemanalyse zur Planarisierung von
Netzwerken (Goetze, Scheffler)
Topologische Einbettung
Übergang
Abstrakter Graph
Menge von Facetten Planaritätsaussage
Topologische Einbettung
1
4
32 65
7
1011 12
13
14 15
16
8 9
F0
F1
F2
F3
F4
F5F6
F7
F8
F9
Topologische Einbettung
F0=(9,11,12)F1=(5,9,6)F2=(12,15,13) . . .F9=(7,16,1,4)
10 2
1
F7
65
9
F1
14 15
16
F3
F4
8
10
14
11 32
8
F5
4
3 5F6
11 12
9
F0
613
7
F8 F9
16
1
4
7
12
15 13F2
Topologische Einbettung
Äußere Facette nicht festgelegt
F9
F0
F1
F2
F3
F4
F5
F6
F7
F8
Topologische Einbettung
F0F9
F6
F5
F7F4
F3
F1
F8
F2
F1
F2
F3
F4
F5
F6 F8
F7F9
F0
DMP-Algorithmus
9
111
3
2
6
5
78
4
10
Gegeben:
2-fachzusammen-hängender
Graph
DMP-Algorithmus
9
111
3
2
6
5
78
4
10
Zyklus
DMP-Algorithmus
9
1
11
3
2
6
5
7
8
4
10
Zyklustopologisch
einbetten
DMP-Algorithmus
9
1
11
3
2
6
5
7
8
4
10
Fragmentierung
DMP-Algorithmus
9
1
11
3
2
6
5
7
8
4
10
Fragmentierung
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
Einbettungder
Fragmente
DMP-Algorithmus
9
1
2
6
5
7
8
4
11
3
10
TopologischeEinbettung
AlsoPlanarität
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
Eine Facettewird alsäußere
deklariert
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
Knoten der äußereFacette werden
auf konvexemPolygon
angepinnt
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
Kräftegleichgewicht
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
x
x
x
x
Triangulierung 3-fach
zusammen-hängend
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
x
x
x
x
Tuttekonvergiert,
Bild ausgewogen
Geometrische Einbettung
9
1
2
6
5
7
8
4
11
3
10
Netzwerke
Hyperkanten
Knoten mit Shapes (z.B. Rechtecke)
Pins; vorgeschriebene Reihenfolge
Knotenhierarchie
Netzwerk: Hyperkanten
Reduktion: Hypergraph Graph
Am Pseudoknoten beliebige Pin-Reihenfolge erlaubt
Netzwerk: fixierte Pins
1
23
4
5 6 7
1
23
4
5
6
7
Netzwerk: fixierte Pins
b d g
e
c
f
a
b
d
g
e
c
f
a
b
d g
e
c
f
a
fecdgbaabgdcefbgdcefa ),,,,,,(),,,,,,(
Pin-Zyklen
Netzwerk: Pin-Restriktionen
c
d
e a
b&
},,,,,{ abedcabecdabdecabdceabcedabcdeMPZ
MPZ(v) = MPZ(Type)
XF-Restriktion: Klasse von fixierten Pins Klasse von freien Pins
Netzwerk: Pin-Restriktionen
c
d
b &
e
f
a &
e
f
a &
c
d
b &
},{},,{,,,},{},,{,, dcfeabfedcba
kontextsensitive Restriktionen
DMP unter Pin-Restriktionen
p1
F0
F1
F2
F3
v
p2 p3
p4
p5
54321 ppppppartCycle
partielle Einbettungen
partielle Pinzyklen
DMP unter Pin-Restriktionen
Zuordnung: Fragment Facette
Ist Zuordnung zulässig?
Sind die eintstehenden partiellen Pin-Zyklen an den beteiligten Kontaktknoten
zulässig?
DMP unter Pin-Restriktionen
p1
F0
F1
F2
F3
v
p2 p3
p4
p5 p
54321' pppppppartCycle
Erweiterbar zu Element von MPZ(v)?
DMP unter Pin-Restriktionen
boolallowedPartialPinCycle (Type type, Partial_Pin_Cycle partCycle);
In DMP wird Backtracking erforderlich
ENDE
