Mikołaj Jachowicz

I will present an overview of a fully dynamic algorithm for maintaining an interval graph in three different representations: minimal interval models, PQ-trees, and modular decomposition. Vertex insertions and deletions are performed in linear time.

1. Christophe Crespelle. Fully Dynamic Representations of Interval Graphs (2019).
2. Müller, Spinrad. Incremental Modular Decomposition (1989).
3. Mikołaj Jachowicz. Fully Dynamic Representations of Interval Graphs. slides. (2026).