Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Frank Kammer, Dieter Kratsch, Moritz Laudahn

We present space-efficient algorithms for computing cut vertices in a given graph with $n$ vertices and $m$ edges in linear time using $O(n+\min \{m,n\log \log n\})$ bits. With the…