Präsentation zu Milestone 1:

Planaritätstest, Planarisierierung undOrthogonalisierung

Gruppenmitglieder:

cku, ocl, pdo, bra

Gliederung

1. Was ist Planarität ?

2. Momentaner Projektstatus• Offene / abgeschlossene Tickets• Grunddatenstruktur

3. Geplante Implementationen• Boyer-Myrvold-Algorithmus• Links-Rechts-Planaritätskriterium• Planarisation durch Knoteneinfügen• Orthogonalisierung von planaren Graphen

Was ist Planarität ?

Def.: Ein Graph ist dann planar, wenn er sich ohne Kantenüberkreuzung zeichnen lässt.

Beispiel:

Projektziele

• Zu gegebenen Graphen überprüfen, ob dieser planar ist (und ggf. planare Einbettung ermitteln)

• Falls der Graph nicht planar ist, diesen z.B. durch Einfügen von zusätzlichen Knoten zu einem planaren Graphen umwandeln

• Darstellung eines planaren Graphen mithilfe eines (quasi-)orthogonalen Ansatzes

Datenstruktur (erste Idee)

Datenstruktur für Boyer /Myrvold

Planare Einbettung über Kanteneinfügen

ocl

Planare Einbettung über Kanteneinfügen

• Basiert auf John M. Boyer, Wendy J. Myrvold: “On the Cutting Edge: Simplified O(n) Planarity by Edge Addition”

• Liefert relativ schnell (lineare Laufzeit) eine planare Einbettung für planare Graphen

• Seit 2004 state-of-the-art Algorithmus für Planaritätstests

Überblick

Tiefensuche erzeugt Baum und ordnet Knoten an Knoten werden in umgekehrter Reihenfolge durchlaufen Zu jedem Knoten wird versucht, die Rückwärtskanten

soweit wie möglich planar einzufügen Ergebnis ist planare Einbettung (wenn möglich) oder

planare Einbettung eines Subgraphen

Der Links-Rechts-Planaritätstest

pdo

Quelle: Brandes, U.: The Left-Right-Planary Test

Der Links-Rechts-Planaritätstest

• Entwickelt von H. de Fraysseix, P. Rosenstiehl, P.O.Mendes

• Algorithmus, der in linearer Zeit auf Planarität testet und ggf. planare Einbettung liefert.

• Aufgrund mangelnder Dokumentation und bislang nur weniger Implementierungen bisher kaum bekannt.

GrundideeDer Graph wird mehrmals mittels DFS durchlaufen:

• 1. Phase: Baum- und Rückwärtskanten werden identifiziert und charakteristische Merkmale (Lowpoints, Verschachtelungsreihenfolge) werden ermittelt.

• 2. Phase: Rückwärtskanten werden unter Berücksichtigung von Konfliktkanten (solche, die nicht überschneidungsfrei in eine Partition passen) rechter oder linker Partition zugeordnet.

Gelingt dies nicht: Graph nicht planar

• 3. Phase: Einbettung (wenn planar) ergibt sich aus Phase 2

Beispiel einer LR-Partition:

Einfügen einer Kante in einen planaren Graphen

cku

Quelle

• C. Gutwenger, P. Mutzel, R. Weiskircher:

"Inserting an edge into a planar graph,"

In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’01), pp. 246-255, 2001.

Planarisierungsmethode

• Lösche Kanten aus Eingabegraphen bis dieser planar ist

• Füge diese nacheinander hinzu und ersetze die möglichst wenigen Kreuzungen mit Dummyknoten mit 4 inzidenten Kanten

• Es liegt jederzeit ein planarer Graph vor• Umwandeln der Dummyknoten in Kreuzungen

ergibt Zeichnung des ursprünglichen Graphen

Einbettungsbeispiele

Bisheriger Ansatz

• Beliebige Einbettung des planaren Graphen gewählt und darin den kürzesten Pfad im dualen Graphen errechnet.

• Problem: für die gewählte Einbettung sind die Kreuzungen minimal. Allerdings kann es für andere Einbettungen bessere Lösungen geben.

Neuer Ansatz

• Minimiert die Anzahl der Kreuzungen über alle Einbettungen

• Nutzung von SPQR-Bäumen

• Anwendung von dualen Graphen:

Grundideen

• Graph wird in Zusammenhangskomponenten (ZHK) zerlegt

• Falls zu verbindende Knoten in unterschiedlichen ZHK liegen so kann man sie verbinden ohne eine Kreuzung zu riskieren

• Falls sie in derselben ZHK liegen greift der Algorithmus

Orthogonales Zeichnen eines

planaren Graphen

bra

Quelle: Klau, G. W.; Mutzel, P.; Quasi-Orthogonal Drawing of Planar Graphs

Orthogonalisierung

• Erster Ansatz entwickelt von R. Tamassia 1987

• Seitdem Entwicklung anderer Ansätze (Giotto, Kandinsky, Quod)

• Orthogonalität aus Gründen der Lesbarkeit und der Ästhetik sehr beliebt

GrundideeAlgorithmus arbeitet mit gegebenem planaren Graphen:

• 1. Phase: Knick-Minimierung (nach Tamassia) durch Flussnetzwerkminimierung

• 2. Phase: Quasi-orthogonale Einbettung des Graphen in ein Gitter