Aktuelles

Erreichbarkeit Sekretariat

Das Sekretariat ist ab Dienstag, den 27.08.19 wieder erreichbar. Prüfungsanmeldungen sind erst dann wieder möglich.

Bei Prüfungsabmeldungen in diesem Zeitraum wenden Sie sich bitte „Planare Graphen“ betreffend an Guido Brückner, „Routenplanung“ betreffend an Jonas Sauer und „Graphentheorie“ betreffend an Sascha Gritzbach.

Nächste Seminare

Geradlinige Gitterzeichnungen planarer Graphen

Beteiligte Mitarbeiter

Beschreibung

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.