Ph.D. thesis : Certifying Graph Algorithms and 3-Connectedness
Advisor: Prof. Dr. Günter Rote
For some important problems on graphs, there are very fast, but complicated algorithms. E.g. testing a graph for planarity or for 3-connectedness has been solved with an optimal asymptotic running time over 30 years ago. But, up to now, there are still contributions dealing with these problems in order to make algorithms more understandable or even to correct some errors in them. When implementing these complex algorithms, it is essential to check if the resulting program does what it should do. A possible way to guarantee the correctness is to find a certificate for each solution that witnesses it and can be automatically checked. For the planarity problem, an embedding in the plane or a Kuratowski subdivision would be such a certificate and so would the separation pair for graphs that are not 3-connected, but what about graphs that are 3-connected? The major task of this thesis is to find such a certificate for 3-connected graphs which is preferably small in size and can be easily checked.