Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs

Abstract

In this paper, we present the clique arrangement A ( G ) for a chordal graph G to describe the intersections between the maximal cliques of G more precisely than in clique trees or related concepts. In particular, the node set of A ( G ) contains a node X = C 1 ∩ C 2 ∩ ⋯ for every set C 1 , C 2 , … of maximal cliques of G . In A ( G ) , there is an arc from a node X to a node Z , if X is a subset of Z and there is no node Y , that is a superset of X and a subset of Z . As clique arrangements may have exponential size, we analyze this notion for strongly chordal graphs G . 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.