A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

摘要

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.