Biconnected Graphs

Definition

How To Determine if Biconnected

O( | E | + | V | )

1. perform DFS, storing the vertices in order visited

2. for each vertex v visited, compute low[v]
       postorder traversal:
       the smallest number of v or a vertex w reachable by following or forward "tree" edges and "back" edge

3. articulation points:
     a) root - 2 or more children
     b) non-root iff child w low[w] >= num[v]

Example

a is root -> articulation point
c - since f
    num[f] >= low[c]
            6            5

Post order traversal

low[e] = min(num[e], num[a], num[b])
          = min(4, 1, 2)
          = 1

low[d] = min(num[d], low[e], num[a])
          = min(3, 4, 1)
          = 1

low[b] = min(num[b], num[d], low[e])
          = min(2, 1, 1)
          = 1

low[g] = min(num[g], num[c])
          = min(7, 5)
          = 5

low[f] = min(num[f], low[g])
          = min(6, 5)
          = 5

low[c] = min(num[c], num[f], low[g])
          = min(5, 5, 5)
          = 5

Return to CIS 350 Index Page