We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity.
Lecture Notes in Computer Science: 6th International Workshop, Wads’99 Vancouver, Canada, August 11–14, 1999 Proceedings, 1999, p. 773-782
Main Research Area:
Lecture Notes in Computer Science
6th International Workshop on Algorithms and Data Structures. WADS 1999