Fully dynamic algorithms for chordal graphs and split graphs

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality; and (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O ( n ) time, where n is the number of vertices. In the second, an insertion query runs in O (log 2 n ) time, an insertion in O ( n ) time, a deletion query in O ( n ) time, and a deletion in O ( n log n ) time. We also present a data structure that allows a deletion query to run in O (√m) time in either implementation, where m is the current number of edges. Updating this data structure after a deletion or insertion requires O ( m ) time. We also present a very simple dynamic algorithm that supports each of the following operations in O (1) time on a general graph: (1) query whether the graph is split, and (2) delete or insert an arbitrary edge.