Finding Bioconnected Components in O9n) Time for a Class of Graphs

A rooted tree is called a  single-branch tree  if there is exactly one nonleaf vertex on each level except the bottom level of the tree. We present an O( n ) time algorithm for finding biconnected components in a graph  G , assuming that a single-branch breadth-first search (SBS) tree of any connected induced subgraph of  G  can be found in O( n ) time. We show that such SBS trees can be found for the interval graphs and the permutation graphs in O( n ) time. Hence, the biconnected components in these graphs can be obtained in O( n ) time, while finding biconnected components in a general graph of  n  vertices and  m  edges takes  O ( n  +  n ) time.