Recognizing the P-4-structure of block graphs

A 4-uniform hypergraph represents the P-4-structure of a graph G, if its hy peredges are the vertex sets of the induced paths P-4 in G. We shall give i n this paper a simple algorithm that recognizes the P-4-structure of a bloc k graph in polynomial time. Here, block graphs are connected graphs in whic h all maximal 2-connected subgraphs are cliques. Our algorithm is based on a similar approach as that for trees by the authors and S. Olariu using wei ghted 2-section graphs of hypergraphs. (C) 2000 Elsevier Science B.V. All r ights reserved.