Geradlinige Gitterzeichnungen planarer Graphen

Dr. Marcus Krug, Prof. Dr. Dorothea Wagner

Für viele Probleme, die sich mithilfe von Graphen modellieren lassen, spielt Visualisierung eine zentrale Rolle. Dabei gelten Zeichnungen, bei denen keine Kreuzungen auftreten und Kanten als Geradensegmente dargestellt werden, als besonders leicht lesbar. Häufig ist man zudem an Gitterzeichnungen interessiert, bei denen die Knoten des Graphen ausschließlich auf einem ganzzahligen Gitter gezeichnet werden dürfen. Solche Gitterzeichnungen treten unter anderem beim Entwurf von Schaltkreisen auf. Die Minimierung der Fläche von geradlinigen Gitterzeichnungen planarer Graphen ist dabei von zentraler Bedeutung.

An unserem Institut beschäftigen wir uns sowohl mit den theoretischen als auch mit den algorithmischen Aspekten dieses Problems. Wir konnten zeigen, dass das Problem der Flächenminimierung geradliniger Gitterzeichnungen planarer Graphen NP-vollständig ist, und haben ein Verfahren entwickelt, mit welchem sich Gitterzeichnungen planarer Graphen kompaktifizieren lassen. Darüber hinaus beschäftigen wir uns mit Algorithmen, die Zeichnungen mit minimaler Fläche approximieren oder diese (für kleine Probleminstanzen) sogar optimal berechnen können.