• 1 Introduction
    • 1.1 Communication-to-Graph Correspondence
    • 1.2 Examples
    • 1.3 Results
  • 2 Preliminaries
    • 2.1 Notation and Terminology
    • 2.2 Communication Complexity
    • 2.3 Boosting & Derandomization
    • 2.4 Equality-Based Labeling Schemes
    • 2.5 Basic Adjacency Sketches
  • 3 Graph Theory & Contextual Results
    • 3.1 The Speed of Hereditary Graph Classes
    • 3.2 Constant-Size Deterministic Labeling Schemes
    • 3.3 Minimal Factorial Families
    • 3.4 The Bell Numbers Threshold
  • 4 Bipartite Graphs
    • 4.1 Equivalence to Bipartite Graphs
    • 4.2 Decomposition Scheme for Bipartite Graphs
    • 4.3 Monogenic Bipartite Graph Families
  • 5 Interval & Permutation Graphs
    • 5.1 Interval Graphs
    • 5.2 Permutation Graphs
  • 6 Graph Products
    • 6.1 Other Graph Products
  • 7 Equality-Based Communication Protocols and Labeling Schemes
    • 7.1 Characterization as Equivalence-Interpretable
    • 7.2 Cartesian Products Do Not Admit an Equality-Based Labeling Scheme
  • 8 Twin-width
    • 8.1 Preliminaries
    • 8.2 From General Graphs to Bipartite Graphs
    • 8.3 Bipartite Graphs of Bounded Twin-width
    • 8.4 First-Order Labeling Schemes & Distance Sketching
  • A Proofs from Section 3
    • A.1 Tools
    • A.2 Classes Below the Bell Number
    • A.3 Minimal Classes Above the Bell Number
  • B Proofs from Section 6
    • B.1 Strong Products
    • B.2 Direct Product
    • B.3 Lexicographic Product
  • C Bibliographic Remark on Greater-Than