Spanner in planaren Graphen

Bei der Optimierung eines Netzwerkes tritt oft die Situation ein, daß man die Menge der bestehenden direkten Verbindungen reduzieren muß, um Kosten zu sparen. Dabei ist es meist unerwünscht, daß sich die Länge des kürzesten Weges zwischen zwei Knoten des Netzwerkes gegenüber der ursprünglichen Entfernung um einen zu großen Faktor erhöht. Für ein Teilnetzwerk bezeichnet man den größten derartig auftretenden Faktor als den sogenannten Streckungsfaktor; sind alle ursprünglich voneinander erreichbaren Knoten auch weiterhin verbunden (wenn auch durch möglicherweise durch längere Wege), so nennt man das Teilnetzwerk einen Spanner des Netzwerkes. Spanner werden schon seit einer Reihe von Jahren algorithmisch untersucht. Neben der Bedeutung für die Netzwerkoptimierung treten sie auch überall da auf, wo man eine große Menge von Informationen über Einzelverbindungen durch eine wesentlich kleinere Zahl ersetzen will, ohne daß dadurch die Information über Kosten oder Entfernungen zu stark geändert wird. Ist man an Spannern minimalen Gewichts interessiert, so sind Baumspanner besonders interessant, d.h. Teilnetzwerke, aus denen keine weiteren Kanten mehr entfernt werden können, ohne daß ursprünglich vorhandene Verbindungen vollständig verloren gehen. Cai und Corneil haben vor einigen Jahren gezeigt, daß die Existenz eines 2-Baumspanners in beliebigen Netzwerken in polynomieller Zeit überprüft werden kann, die Entscheidung über die Existenz eines 4-Baumspanners hingegen NP-vollständig ist. Die Komplexität von 3-Baumspannern in beliebigen Netzwerken ist schon seit längerem offen. Eine Klasse von Netzwerken von großer Bedeutung sind die sogenannten planaren Graphen - also Netzwerke, die ohne Überkreuzung von Kanten in der Ebene darstellbar sind. Da es in planaren Graphen besonders einfache Beziehungen zwischen den in einem Baumspanner verbleibenden und den entfernten Kanten gibt (die entfernten Kanten bilden einen Baumspanner des Dualgraphen), war es durchaus denkbar, daß für diese Graphenklasse schnelle Algorithmen zur Auffindung guter Baumspanner existieren. Es gelang uns aber nachzuweisen, daß die Frage nach einem Baumspanner mit optimalem Stretchfaktor bereits für planare Graphen NP-schwer ist. Andererseits entwickelten wir einen Algorithmus, der in polynomieller Zeit entscheidet, ob ein planarer Graph einen 3-Baumspanner hat. Zumindest für diesen Spezialfall konnten wir also eine positive Antwort auf das Problem von Cai und Corneil finden.