A vertex incremental approach for maintaining chordality Original Research Article

For a chordal graph G=(V,E)G=(V,E), we study the problem of whether a new vertex u∉Vu∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uvuv, a characterization of the set of edges incident to u that also must be added to G along with uvuv. We propose a data structure that can compute and add each such set in O(n)O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm)O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.