Donnerstag, 09.11.2000, 13:00, SG 00-90

PD Dr. Elias Dahlhaus

Institut für Informatik

Universität Bonn

"Geclusterte planare Graphen"

Abstract:

Um komplexe Graphenstrukturen darzustellen, unterteilt man sie rekursiv in Cluster.

Anwendungen gibt es

1. im VLSI-Entwurf: Cluster entsprechen Bausteinen und möglicherweise Bausteinen von Bausteinen.
2. in der Darstellung von Verkehrsnetzen: Teilverkehrsnetze großer Dichte fasst man als Cluster auf.

In diesem Vortrag geht es darum, geclusterte Graphen kreuzungsfrei in die Ebene einzubetten, so dass die Cluster zusammenhängende Gebiete ohne Löcher bilden (geclusterte planare Einbettung). Nicht jeder geclusterte Grasph hat eine geclusterte planare Einbettung. Es kann aber sehr effizient

1. festgestellt werden, ob ein gegebener geclusterter Graph eine geclusterte planare Einbettung besitzt und
2. eine geclusterte planare Einbettung berechntet werden.