Structure and constructions of 3-connected graphs

Abstract

The class of 3-connected (i.e., 3-vertex-connected) graphs has been studied intensively for many reasons in the past 50 years. One algorithmic reason is that graph problems can often be reduced to handle only 3-connected graphs; applications include problems in graph drawing, problems related to planarity and online problems on planar graphs. It is possible to test a graph on being 3-connected in linear time. However, the linear-time algorithms known are complicated and difficult to implement. For that reason, it is essential to check implementations of these algorithms to be correct. A way to check the correctness of an algorithm for every instance is to make it certifying, i. e., to enhance its output by an easy-to-verify certificate of correctness for that output. However, surprisingly few work has been devoted to find certifying algorithms that test 3-connectivity; in fact, the currently fastest algorithms need quadratic time. Two classic results in graph theory due to Barnette, Grünbaum and Tutte show that 3-connected graphs can be characterized by the existence of certain inductively defined constructions. We give new variants of these constructions, relate these to already existing ones and show how they can be exploited algorithmically. Our main result is a linear- time certifying algorithm for testing 3-connectivity, which is based on these constructions. This yields also simple certifying algorithms in linear time for 2-connectivity, 2-edge-connectivity and 3-edge-connectivity. We conclude this thesis by a structural result that shows that one of the constructions is preserved when being applied to depth-first trees of the graph only.

Die Klasse der 3-zusammenhängenden Graphen ist aus vielen Gründen seit 50 Jahren Gegenstand aktiver Forschung. Ein algorithmisch geprägter Grund ist, dass viele Graphenprobleme auf 3-zusammenhängende Graphen reduziert werden können. Anwendungen finden sich beispielsweise bei Graphzeichnungsproblemen und Problemen auf planaren Graphen. Ein Graph kann in Linearzeit auf 3-Zusammenhang überprüft werden. Allerdings sind die bekannten Linearzeitalgorithmen kompliziert und schwierig zu implementieren. Aus diesem Grund ist es unabdingbar, Implementationen dieser Algorithmen auf Korrektheit zu überprüfen. Eine Möglichkeit, die Korrektheit jeder Probleminstanz zu überprüfen, ist, den Algorithmus zertifizierend zu machen. Ein zertifizierender Algorithmus ist ein Algorithmus, der neben der Ausgabe zusätzlich ein leicht zu verifizierendes Korrektheitszertifikat dieser Ausgabe liefert. Trotz zahlreicher Anwendungen 3-zusammenhängender Graphen wurden zertifizierende Algorithmen, die 3-Zusammenhang testen, bisher kaum untersucht; die schnellsten bekannten Algorithmen benötigen quadratische Laufzeit. Zwei klassische Resultate aus der Graphentheorie von Barnette, Grünbaum und Tutte charakterisieren 3-zusammenhängende Graphen durch die Existenz induktiv definierter Konstruktionen. Wir untersuchen neue Varianten dieser Konstruktionen, stellen diese zu den klassischen Resultaten in Beziehung und zeigen, wie die Konstruktionen algorithmisch genutzt werden können. Der Hauptbeitrag dieser Arbeit ist ein auf diesen Konstruktionen basierender, zertifizierender Algorithmus, der Graphen auf 3-Zusammenhang in Linearzeit testet. Dieser kann auf k-Zusammenhang und k-Kantenzusammenhang für k > 3 erweitert werden. Abschließend zeigen wir als Strukturresultat, dass eine der vorgestellten Konstruktionen erhalten bleibt, wenn sie nur auf einen Teil des Graphen, nämlich einen Tiefensuchbaum, angewendet wird.