Space efficient algorithms for some graph theoretical problems

Summary We present space-efficient-O(log² n)-deterministic algorithms for some graph theoretical problems such as planarity testing, producing a plane embedding, finding minimum cost spanning trees, obtaining the connected, biconnected and triconnected components of a graph. Previous planarity algorithms used (n) space. Several algorithms are based on a space-efficient matrix inversion method. The same bounds hold for uniform circuit depth.Research partially supported by NSF grants No. MCS 79-05006 and MCS 78-27600.