Birgit Engels
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Dünne geometrische Graphen mit kleiner Dilatation

Wir betrachten einen geometrischen Graphen G=(P, E) in der Ebene, d.h. Punkte P in der Ebene als Knoten und Kanten (p,q), deren Gewicht dem euklidischen Abstand d(p,q) ihrer Endpunkte entspricht.

Die Dilatation D(p,q) eines Punktepaares (p,q) ist ein Mass fuer den "Umweg", den man von p nach q geht, wenn man sich nur auf den Kanten des Graphen fortbewegt: D(p,q)=dG(p,q)/d(p,q), wobei dG(p,q) der Laenge eines kuerzesten Weges von p nach q ueber die Kanten in E entspricht. Die Dilatation D(G) eines Graphen ist dann das Maximum der Dilatationen D(p,q) ueber alle Punktpaare in P.

Ein vollstaendiger Graph besitzt die "beste" Dilatation (1), da fuer jedes Punktepaar ein direkter Weg existiert. In Anwendungen (Netzwerke, Bewegungsplanung, ...) kann ein vollstaendiger Graph jedoch teuer sein. Daher werde ich einen Artikel von Aronov et al. vorstellen, in dem Schranken (abhaengig von n) fuer die Dilatation von duennen Graphen betrachtet werden.