Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 11.12.2007 Besprechung: 15.01.2007 Gruppe 2 - Übungsblatt

Martin Böhmer/Dennis Treder/Marina Schwacke

Übungen zu Automatisches Zeichnen

von Graphen

Ausgabe: 11.12.2007 — Besprechung: 15.01.2007

Gruppe 2

- Übungsblatt 5 -


Aufgabe 3: Knotenpositionierung

Erläutern Sie den Mixed-Model Algorithmus, der in der Publikation

C. Gutwenger und P. Mutzel: Planar Polyline Drawings with Good Angular Resolution, In S. Whitesides (Eds.), Proceedings Graph Drawing, Montreal, Canada., Lecture Notes in Computer Science, vol. 1547, Springer, 1998, 167-182,beschrieben ist.

Welche Eigenschaften besitzen die entstehenden Zeichnungen?


Gliederung

Einleitung

Mathematische Grundlagen

Algorithmus

Analyse

Kommentar


Einleitung: Mixed Model Algorithmus

Linearzeit-Algorithmus erstellt Polyline-Gitterzeichnung von jedem

planaren Graphen Phasen

VorbereitungsphaseErweiterung auf 2-zusammenhängenden,ebenen Graphen

kanonische Ordnung der Knotenbounding boxes um KnotenPlatzierung der Knoten


Einleitung: Idee des Algo

basiert auf Ideen von Kant für3-zusammenhängene Graphen: ebenfalls Linearzeit-Algorithmus minimaler Winkel mind. 2 / d

d = maximaler Knotengrad des Graphen maximal 3 Knicke pro Kante Kantenlänge O(n)

n = Anzahl Konten des Graphen MixedModell mit Polylines aus straightline

Framework und kanoischer Ordnung für 3-zusammenhängende Graphen entstanden


Einleitung: Andere Ansätze für d > 4

Knoten als Boxen

Nachteile sehr große Knoten teilweise ist Größe

vom Gradunabhängig



Grob- und Feingitter

Nachteile Linien sehr (zu)

nah beisammen kein polynomieller

Algorithmus bekannt



Kurze, diagonaleLinien

Nachteil Winkel zu klein



Graph G heißt einfach, wenn G weder mehrfache Kanten noch Kreise enthält.

G ist flach, wenn G mit planarer Zeichnung verbunden ist.

Die Einbettung eines planaren Graphen G, ist die Sammlung von kreisförmigen Ordnungen der inzidenten Kanten oder Knoten um jeden Knoten in einer planaren Zeichnung von G.

Ein flacher Graph teilt die Fläche in Regionen, genannt Facesunbegrenztes Face = äußeres Face,sonst inneres Face



Für einen Knoten v aus G benutzen wir die Kreisordnung gegen den Uhrzeigersinn

Die Grenze im Uhrzeigersinn eines Faces f ist ein Kreisdurchlauf v0e1v1...ekvk entlang der Kanten von f, so dass vi+1 der Nachfolger von vi−1 in der Ordnung gegen den Uhrzeigersinn von vi ist.

Ein zusammenhängender Graph G wird k-zusammenhängend genannt, wenn er, nach Löschen von k-1 beliebigen Knoten, immer noch zusammenhängend istFür k=2 und k=3: bi- / tri-zusammenhängend


Der Algorithmus

Eingabe: G = (V, E), wobei G flach und einfach Drei Phasen

1. Berechne geordnete Partition π= disjunkte Teilmengen von V

2. Bestimme Bounding Boxes der Knoten= Berechnung von Inpoints und Outpoints

3. Platzierung= Koordinaten der Knoten berechnen


Phase 1: Die geordnete Partition π

π = (V1, …, VN)mit und

Gk = V1 … Vk sei planarer Subgraph rank(v) = Index i für das Vi das v enthält

Eigenschaften von π(P1) Für jedes Vk = {z1, …, zp) existieren zwei Knoten

left(Vk) und right(Vk) mit:E1(Vk) = {(zi, zi+1)|1 ≤ i < p} für k ≥1E2(Vk) = {(left(Vk), z1), (zp, right(Vk))} für k ≥ 2

left(Vk) right(Vk)z1 zp…



Eigenschaften von π(P1 Forts.)

kann in G eingefügt werden ohne Kreuzungen zu erzeugen. mit

(P2) V1 = {v1, ..., vs} ist ein Pfad auf der Grenze im Uhrzeigersinn des externen Faces von .Die Knoten in Vk (k ≥ 2) liegen auf dem externen Face von .



Eigenschaften von π(P3) C1 ist Sequenz von v1, ..., vs.

Für k ≥ 2 sei Ck−1 = c1, ..., cq bereits definiert.Sei cl = left(Vk) und cr = right(Vk).Dann ist Ck die Sequenz c1, ..., cl, Vk, cr, ..., cq.

(P4) Sei Vk = {z1, ..., zq}.a)

b) Sei k ≥ 2, Ck−1 = c1, ..., cq, left(Vk) = cl, right(Vk) = cr. Dann liegen alle Nachbarn von Vk in in {cl, ..., cr}. Wenn p ≥ 2, dann hat Vk genau zwei Nachbarn in .


Phase 1: Die kanonische Ordnung

π ist eine kanonische Ordnung, wenn gilt:(1) V1 = {v1, ..., vs}, wobei v1, ...vs ein Pfad auf der Grenze im

Uhrzeigersinn des externen Faces von G mit s ≥ 2 undE({v1, ..., vs}) = {(vi, vi+1) | 1 ≤ i < s}.

(2) Jeder Subgraph Gk ist zusammenhängend und intern 2-zusammenhängend

(3) Bezeichne C‘k den Pfad auf der Grenze gegen den Uhrzeigersinn des externen Faces von Gk ausgehend von Knoten v1 zu Knoten vs. Für jedes 2 ≤ k ≤ N trifft zu eine der Bedingungen zu, wobei C‘k = [v1 = c1, ..., cq = vs]:

a) Vk = {z} und z ist ein Knoten aus C‘k mit mindestens drei Nachbarn in Gk−1

b) Vk = {z1, ..., zp} C‘k, p ≥ 1, und es existieren Knoten cl, cr, l < r, aus C‘k, so dass cl, z1, ..., zi, u1, ..., uj , zi+1, ..., zp, cr ein Pfad auf der Grenze im Uhrzeigersinn des Faces aus G für 0 ≤ i ≤ p, j ≥ 0. u1, ..., uj sind Knoten aus G \ Gk und


Phase 1: Die kanonische Ordnung

G ist u.U. nicht 2-zusammenhängend (für Ordnung erforderlich) Erweiterung auf 2-zusammenhängenden Graphen G‘ = (V, E‘)

Berechnung der Ordnung Berechnung von left(Vk) und right(Vk)

Seien Ck−1 = c1, ..., cq und e1, ..., ea die Kanten in G' miteμ = (vμ, ciμ) und vμ aus Vk, so dass i1 < ... < ia.

a ≤ 2, Vk erfüllt die Definition (3b)left(Vk) := cl und right(Vk) := cr,wobei cl und cr die Knoten sind, die nach (3b) existieren

a ≥ 3left(Vk) := cl und right(Vk) := cr, mit l und r wie folgt:Sei N = {ciμ|eμ aus E}.

N = {}: l := i1 und r := ia. N = {ct}:

|N| ≥ 2: l := min{μ | cμ aus N} und r := max{μ | cμ aus N}.


Phase 2: Inpoints und Outpoints

In- und Outpoints beschreiben Bounding Box eingehende Kante: {(v,w) | rank(w) ≤ rank(v)} ausgehende Kante: {(v,w) | rank(w) > rank(v)} in(v) = Anzahl der eingehenden Kanten von v,

out(v) = Anzahl der ausgehenden Kanten von v Koordinaten der In- und Outpoints sind

relativ zur Position von v (v,w) mit rang(v) = rang(w),

zwei Inpoints und keinenOutpoint setzen horizontale Kante


Phase 2: Outpoints

Sei Vk = {z1, ..., zp}, v = zi, z0 := left(Vk) und zp+1 := right(Vk)outl(v), outr(v), δl, δr berechnen sich wie folgt:

Wenn out(v) ≥ 1, werden folgende Punkte platziert:• outl(v) Outpoints mit den Koordinaten

(− outl(v), δl), ..., (−1, outl(v) + δl − 1) (Geraden mit Steigung 1)• Einen Outpoint auf Punkt (0, max{outl(v) + δl − 1, outr(v) + δr − 1})• outr(v) Outpoints mit den Koordinaten

(1, outr(v) + δr − 1), ..., (outr(v), δr), (Geraden mit Steigung -1)


Phase 2: Inpoints

Wenn in(v) ≤ 3,alle Inpoints auf (0,0) setzen

Andersfalls,• Einen Inpoint auf Punkt (−inl(v), 0).• inl(v) Inpoints mit den Koordinaten

(−inl(v), −1), ..., (−1, −inl(v)),welche auf einer Geraden mit Steigung -1 liegen

• Einen Inpoint auf den Punkt (0, −inr(v))• inr(v) Inpoints mit den Koordinaten

(1, −inr(v)), ..., (inr(v), −1),welche auf einer Geraden mit der Steigung +1 liegen

• Einen Inpoint auf Punkt (inr(v), 0)


Phase 2: Beispiele


Phase 2: Beispiele


Phase 3: Platzierung

Verwenden von absoluten y-Koordinaten und relativen x-Koordinaten

Berechnen der x-Koordinaten:Sei C = c1, ..., cq die gegenwärtige Kontur

(1)



Verschieben von Knoten: ci aus C nach rechts verschieben-> ci,...,cq und einige Knoten die nicht aus C sind

M(ci) die Menge von Knoten die verschoben werden müssen, wenn ci verschoben wird. -> Baum mit Wurzel ci, Knoten sind relativ zur Wurzel

Alle Mengen M(ci) mit 1≤i≤q, sind ein Wald F von allen Knoten, wobei die Wurzeln die Knoten aus C sind.

father(v) ist der Vorgänger von v in F, mit rang(father(v))>rang(v)

Absolute x-Koordinaten mit (1) berechnen, durch: entlanglaufen der Knoten in C und dann aller anderen Knoten nach absteigendem Rang



Algorithmus Mixed-Model-PlacementInput: Ein planarer Graph G=(V,E), eine geordnete Partition∏ = V1,...,VN von G (die P1 bis P4 erfüllt) und in- und outpoints.

Output: Absolute y- und relative x-Koordinaten gemäß der Gleichung (1) für jeden Knoten in G.

Initalisierung: Wir setzen die Menge V1 = {v1,...,vs}. Wir setzen



for k:=2 to N do Sei C=c1,...,cq Vk={z1,...,zp}, cl=left(Vk) und cr=right(Vk). y-Koordinaten setzen: vorläufige x-Koordinaten berechnen von cl+1,...,cr relativ zu cl.

if in(z1) ≥ 3 theneinen einzelnen Knoten platzierenelsep≥1 Knoten mit maximal zwei Nachbarn von C platzierenfi

C := c1,...,cl,z1,...,zq,cr,...,cq

od



if in(z1) ≥ 3 then (einen einzelnen Knoten platzieren )

Wir wollen z1 direkt über ut plazierensetzen ut = outpoint(ct,z1) und dxt = ut.dx

Überprüfen ob z1 direkt über ut plaziert ist:δ = x(z1) − (x(ct) + dxt).if δ > 0 then z1 liegt rechts von ut -> δ Einheiten nach rechts verschieben.

Knoten cl+1,...,cr−1 verschwinden aus C, ihre x-Koordinatenrelativ zu z1 setzen und den Baum F updaten:



else(p≥1 Knoten mit maximal zwei Nachbarn von C platzieren)

Knoten cl+1,...,cr−1 verschwinden aus C, ihre x-Koordinatenrelativ zu z1 setzen und den Baum F updaten:


Analyse

Soweit uns bekannt erreicht dieser Algorithmus die bestenGrenzen für Gittergröße, Winkelauflösung und die Anzahlvon Knicken für planare, dichte Graphen.Der Algorithmus zeichnet einen d-planarenGraphen G so in ein Gitter:• dass jede Kante höchstens drei Knicke hat,• dass der minimale Winkel zwischen zwei Kanten

mindestens 2/d (Bogenmaß) beträgt,• die Gittergröße (2n-5) x (3/2n-7/2) ist• er höchstens 5n-15 Knicke besitzt• und jede Kante Länge O(n) hat (n = Anzahl Knoten von G)

Der Algorithmus benötigt lineare Laufzeit.


Kommentar

Graphen sind im Allgemeinen nicht planar! Graphen in planare Graphen umgewandeln. Kreuzungen ersetzen.

Mögliche Planarisierungsmethode:

Maximum planare Subgraph Problem lösen und die gelöschten Kanten wieder einzufügen.

Beim Mixed-Model Algorithmus können die Zeichnungen dann seltsam aussehen und es ist schwierig die Kreuzungen zu erkennen.-> Algorithmus modizieren:

Künstlich erzeugten Knoten anders behandeln Erstrebenswert Mixed-Modell-Zeichnungen bei der Kanten

nicht ihre Kreuzungsknoten knicken dürfen.

Documents

Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 11.12.2007 Besprechung: 15.01.2007 Gruppe 2 - Übungsblatt