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.
Partially supported by the ESPRIT Long Term Research Program of the EU under contract 20244 (project ALCOM-IT).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1–16, 1997.
Boliong Chen, Makoto Matsumoto, Jian Fang Wang, Zhong Fu Zhang, and Jian Xun Zhang. A short proof of Nash-Williams‘theorem for the arboricity of a graph. Graphs Combin., 10(1):27–28, 1994.
Chuang, Garg, He, Kao, and Lu. Compact encodings of planar graphs via canonical orderings and multiple parentheses. In ICALP: Annual International Colloquium on Automata, Languages and Programming, 1998.
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms, chapter 23. MIT Press, Cambridge, Mass., 1990.
Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of the Association for Computing Machinery, 31(3):538–544, 1984.
Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465–497, 1992.
Grossi and Lodi Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121–132, 1998.
Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.
Peter Bro Miltersen. Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 556–563, 1998.
J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In 38th Annual Symposium on Foundations of Computer Science, pages 118–126, 20-22 October 1997.
C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. The Journal of the London Mathematical Society, 36:445–450, 1961.
C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. The Journal of the London Mathematical Society, 39:12, 1964.
J. C. Picard and M. Queyranne. A network ow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141–160, 1982.
M. Talamo and P. Vocca. Compact implicit representation of graphs. In Graph-Theoretic Concepts in Computer Science, volume 1517 of Lecture Notes in Computer Science, pages 164–176, 1998.
G. Turan. Succinct representations of graphs. Discrete Applied Math, 8:289–294, 1984.
Jan van Leeuwen. Graph algorithms. In Handbook of Theoretical Computer Science, vol. A: Algorithms and Complexity, pages 525–631. North-Holland Publ. Comp., Amsterdam, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodal, G.S., Fagerberg, R. (1999). Dynamic Representations of Sparse Graphs. In: Dehne, F., Sack, JR., Gupta, A., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1999. Lecture Notes in Computer Science, vol 1663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48447-7_34
Download citation
DOI: https://doi.org/10.1007/3-540-48447-7_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66279-2
Online ISBN: 978-3-540-48447-9
eBook Packages: Springer Book Archive