A fully dynamic algorithm for recognizing and representing proper intervalgraphs

In this paper we study the problem of recognizing and representing dynamica lly changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modi cation ca n be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper inter val graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclu sion-free family of intervals. This problem has important applications in p hysical mapping of DNA. We give a near-optimal fully dynamic algorithm for this problem. It operate s in O(log n) worst-case time per edge insertion or deletion. We prove a cl ose lower bound of Omega (log n/(log log n + log b)) amortized time per ope ration in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each e dge operation in O(1) time. As a byproduct of our algorithm, we solve in O ( log n) worst-case time the problem of maintaining connectivity in a dynam ically changing proper interval graph.