Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

2016/06/15 by Frank Kammer, Kammer, Frank, Dieter Kratsch +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #cs.DS

paper · pdf · doi:10.48550/arxiv.1606.04679

arxiv created 2016/12/08 · arxiv updated 2016/12/09

Abstract

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,nlog log n\) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(nlog log n) time using O(n) bits.

Cited by

• Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Related

• Improved Linear-Time Algorithm for Computing the 4-Edge-Connected Components of a Graph
• On finding 2-cuts and 3-edge-connected components in parallel
• Computing bounded-width tree and branch decompositions of k-outerplanar graphs
• Contracting a Planar Graph Efficiently
• Determining 4-edge-connected components in linear time