• Introduction
    • Communication Complexity
    • Implicit Graph Representations
    • Subsequent Work
    • Organization
  • Preliminaries
    • Notation and Terminology
    • Communication Complexity
    • Adjacency Labeling Schemes, Universal Graphs, and Factorial Classes
  • Connections: Randomized Communication and Implicit Representations
    • Adjacency Sketching and Probabilistic Universal Graphs
    • Communication-to-Graph Correspondence
      • Chain Number & Stability
    • Reductions
      • Between communication problems
      • Between graph classes
    • Equality-Based Labeling Schemes
    • Basic Adjacency Sketches
  • Question I. New Examples of Constant-Cost Communication
    • Computing Small Distances and First-Order Formulae
      • Preliminaries
      • From General Graphs to Bipartite Graphs
      • Bipartite Graphs of Bounded Twin-width
      • First-Order Labeling Schemes & Distance Sketching
    • Graph Products
  • Question II. Structure: Stability is Sometimes Sufficient
    • Interval & Permutation Graphs
      • Interval Graphs
      • Permutation Graphs
    • Monogenic Bipartite Graphs
      • Decomposition Scheme for Bipartite Graphs
      • Monogenic Classes of Bipartite Graphs
      • S 1,2,3-Free Bipartite Graphs
      • F p,q-Free Bipartite Graphs
      • P7-Free Bipartite Graphs
  • Question III. Equality is Not Complete
  • References
  • Missing Proofs from Section 3
    • Probability Boosting and Derandomization
    • Lower Bound from Greater-Than
      • Proof of the lower bound
      • Bibliographic remark on Greater-Than
    • Missing Proof for Equality-Based Labeling
  • The Lattice of Hereditary Graph Classes
    • The Speed of Hereditary Graph Families
    • Minimal Factorial Families