A dynamic distributed approach to representing proper interval graphs

First studied by Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representation of sparse graphs, in: Algorithms and Data Structures, Proceedings of the 6th International Workshop, Vancouver, Canada, in: Lecture Notes in Computer Science, vol. 1663, Springer-Verlag, 1999], a dynamic adjacency labelling scheme labels the vertices of a graph so that the adjacency of two vertices can be deduced from their labels. The scheme is dynamic in the sense that only a small adjustment must be made to the vertex labels when a small change is made to the graph.Using a centralized dynamic representation of Hell, Shamir and Sharan [P. Hell, R. Shamir, R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM Journal on Computing 31 (1) (2001) 289–305], we develop a O(logn) bit/label dynamic adjacency labelling scheme for proper interval graphs. Our fully dynamic scheme handles vertex deletion/addition and edge deletion/addition in O(n) time. Furthermore, our dynamic scheme is error-detecting, as it recognizes when the new graph is not a proper interval graph.