Breaking Graphs into Independent Rectangles

We survey the problem of covering and partitioning a bipartite graph using vertex-disjoint unions of bicliques. The concept of a vertex-disjoint union of bicliques has been given many names in computer science: it has been termed a blocky matrix in communication complexity,

a fat matching in circuit complexity, a bipartite P4-free graph in graph theory, a simple graph in cryptography, and a bicluster in bioinformatics. We aim to unify all of these perspectives, compiling what is known and unknown about the problem, including discussion on upper and lower bounding techniques for the problem, bounds for specific families of graphs, and

the hardness of computation of the problem. Along the way, we present a new explicit graph for which the covering and partitioning numbers are different.