Dynamic Representations of Sparse Graphs

Gerth Stølting Brodal and Rolf Fagerberg

In Proc. 6th International Workshop on Algorithms and Data Structures, volume 1663 of Lecture Notes in Computer Science, pages 342-351. Springer Verlag, Berlin, 1999.

Abstract

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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 1999. All rights reserved.

Online version

wads99.pdf (207 Kb)

DOI

10.1007/3-540-48447-7_34

Links

BIBTEX entry

@incollection{wads99,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 6th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/3-540-48447-7_34",
  isbn = "978-3-540-66279-2",
  pages = "342-351",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Dynamic Representations of Sparse Graphs",
  volume = "1663",
  year = "1999"
}