Algorithmen für planare Graphen

Universit¨t Karlsruhe a Fakult¨t f¨r Informatik a u

Institut f¨r Theoretische Informatik u Algorithmik I

Vorlesungsskript

Algorithmen fur planare Graphen ¨

Dorothea Wagner Sommersemester 2008

a

u

v

b

Inhaltsverzeichnis

1 Planare Graphen – eine anschauliche Einf¨hrung u 2 Grundlegende Eigenschaften planarer Graphen 2.1 Grundlegende Eigenschaften . . . . . . . . . 2.2 Charakterisierung planarer Graphen . . . . . 2.3 Dualgraph . . . . . . . . . . . . . . . . . . . 2.4 Suchmethoden in planaren Graphen . . . . . 3 F¨rbung planarer Graphen a 4 Separatoren in planaren Graphen 5 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 11 11 14 23 25 29 33 43

6 Mixed Max Cut und Via-Minimierung 47 6.1 Mixed-Max-Cut in planaren Graphen . . . . . . . . . . . . . . . . . . . . 48 6.2 Das Via-Minimierungs-Problem . . . . . . . . . . . . . . . . . . . . . . . 54 7 Das Menger-Problem 62 7.1 Das kantendisjunkte Menger-Problem in planaren Graphen . . . . . . . . 63 7.2 Das knotendisjunkte Menger-Problem . . . . . . . . . . . . . . . . . . . . 71 8 Das Problem von Okamura und Seymour 80

---

Inhaltsverzeichnis Vorwort: Dieses Vorlesungsskript ist auf Basis der gleichnamigen Vorlesung entstanden, die ich im Sommersemester 1997 und im Sommersemester 2001 an der Universit¨t a Konstanz und im Sommersemester 2006 an der Universit¨t Karlsruhe gehalten habe. a Frau L¨thke hat aus meinen handschriftlichen Unterlagen eine erste Version des Skripts u erstellt, und Herr Stefan Schmidt hat die Abbildungen angefertigt. Ihnen gilt mein Dank f¨r diese Unterst¨tzung. u u

---