Adjacency queries in dynamic sparse graphs

We deal with the problem of maintaining a dynamic graph so that queries of the form “is there an edge between u and v?” are processed fast. We consider graphs of bounded arboricity, i.e., graphs with no dense subgraphs, like, for example, planar graphs. Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representations of sparse graphs, in: Proc. 6th Internat. Workshop on Algorithms and Data Structures (WADS'99), in: Lecture Notes in Comput. Sci., vol. 1663, Springer, Berlin, 1999, pp. 342–351] described a very simple linear-size data structure which processes queries in constant worst-case time and performs insertions and deletions in O(1) and O(logn) amortized time, respectively. We show a complementary result that their data structure can be used to get O(logn) worst-case time for query, O(1) amortized time for insertions and O(1) worst-case time for deletions. Moreover, our analysis shows that by combining the data structure of Brodal and Fagerberg with efficient dictionaries one gets O(logloglogn) worst-case time bound for queries and deletions and O(logloglogn) amortized time for insertions, with size of the data structure still linear. This last result holds even for graphs of arboricity bounded by O(logkn), for some constant k.