Fakultät für Mathematik und Informatik Universität Leipzig
Institut für Informatik UNIVERSITÄT LEIPZIG
Vortragsserie zu Parallelverarbeitung und Komplexen Systemen

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.

Vorhergehende Seite Seitenanfang HomePage Suchen 2003-01-06   © Andreas Zerbst