• 1 Introduction
    • 1.1 Our Results
    • 1.2 Related Work
  • 2 Preliminaries
    • 2.1 Empirical Entropy
    • 2.2 Preferential-Attachment Graphs
    • 2.3 Succinct Data Structures
  • 3 Space Lower Bound
    • 3.1 Proof of Theorem 1.1
  • 4 Data Structures
    • 4.1 Construction
    • 4.2 Operations
  • 5 Conclusion
  • References
  • Appendix
    • A Proof of Theorem 1.2 (Lower Bound for Unlabelled PA Graphs)
    • B Space and Time Analysis of our Data Structure
    • C Proof of Lemma B.2 (Tree Deletion)
      • C.1 Blocked Character Deletion
      • C.2 Least-Frequent-Character (LFC) Scheme
      • C.3 Analysis