Good characterizations and linear time recognition for 2-probe block graphs

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G=(V,E) is said to be an (unpartitioned) k-probe block graph if there exist k independent sets Ni⊆V, 1≤i≤k, such that the graph G′ obtained from G by adding certain edges between vertices inside the sets Ni, 1≤i≤k, is a block graph; if the independent sets Ni are given, G is called a partitioned k-probe block graph. In this paper we give good characterizations for 2-probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011).