Space-efficient static trees and graphs
G. Jacobson · Annual Symposium on Foundations of Computer Science · 1989
Data structures that represent static unlabeled trees and planar graphs are developed. The structures are more space efficient than conventional pointer-based representations, but (to within a constant factor) they are just as time efficient for traversal operations. For trees, the data structures described are asymptotically optimal: there is no other structure that encodes n-node trees with fewer bits per node, as N grows without bound. For planar graphs (and for all graphs of bounded page number), the data structure described uses linear space: it is within a constant factor of the most succinct representation.>
Cited by 634 works. doi:10.1109/sfcs.1989.63533
Authors
References
- The Design and Analysis of Computer Algorithms
- Storing a sparse table
- Efficient Storage and Retrieval by Content and Address of Static Files
- On the succinct representation of graphs
- The book thickness of a graph
- Succinct representations of graphs
- Implicat Representation of Graphs
- THE CODING OF VARIOUS KINDS OF UNLABELED TREES
- Four pages are necessary and sufficient for planar graphs