Characterizing and computing the structure of clique intersections in strongly chordal graphs

In this paper, we present the clique arrangement A(G)A(G) for a chordal graph GG to describe the intersections between the maximal cliques of GG more precisely than in clique trees or related concepts. In particular, the node set of A(G)A(G) contains a node X=C1∩C2∩⋯X=C1∩C2∩⋯ for every set C1,C2,…C1,C2,… of maximal cliques of GG. In A(G)A(G), there is an arc from a node XX to a node ZZ, if XX is a subset of ZZ and there is no node YY, that is a superset of XX and a subset of ZZ.As clique arrangements may have exponential size, we analyze this notion for strongly chordal graphs GG. We provide a new characterization of strongly chordal graphs in terms of forbidden cyclic structures in the corresponding clique arrangements and we show how to compute the clique arrangement of a strongly chordal graph efficiently.