Obwohl kürzeste Wegeprobleme im Rahmen der Graphentheorie bereits ausführlich untersucht wurden, werden in den letzten Jahren im Zusammenhang mit Verkehrsinformationssystemen neue Lösungsansätze entwickelt. Dabei legt man in einer Preprocessing-Phase hierarchische Strukturen für ein gegebenes Verkehrsnetz an, so daß die kürzeste Wegesuche in dem Verkehrsnetz mit dieser Struktur effizienter erfolgen kann.

Wir führen für ungerichtete Graphen hierarchische und regionenhierarchische Graphen ein. In planaren hierarchischen und regionenhierarchischen Graphen kann die kürzeste Entfernung zwischen zwei Knoten in einer Laufzeit von O(n^{0.5}) ermittelt werden (n sei die Anzahl der Knoten in dem gegebenen Graphen). Der kürzeste Weg mit l Knoten kann in O(n^{0.5} + l) Operationen berechnet werden. Beide Typen von hierarchischen Graphen benötigen O(n^{1.5}) Platz für die Speicherung der Hilfstabellen. Während für den Aufbau von allgemeinen planaren hierarchischen Graphen O(n^2) Operationen benötigt werden, kann der Aufbau von planaren regionenhierarchischen Graphen in O(n^{1.5}) Operationen erfolgen. Beim Aufbau der hierarchischen Graphen benutzen wir insbesondere ein Separatortheorem von Lipton und Tarjan von 1979.

Die Ergebnisse wurden anhand von Experimenten mit realen Straßendaten nachgewiesen