###
Compact Binary Relation Representations with Rich Functionality

####
Jérémy Barbay, Francisco Claude, and Gonzalo Navarro

Binary relations are an important abstraction arising in many
data representation problems.
The data structures proposed so far to represent them support just a few
basic operations required to fit one particular application.
We identify many of those operations arising in applications and generalize
them into a wide set of desirable queries for a binary relation
representation. We also identify reductions among those operations.
We then introduce several novel binary relation representations, some simple
and some quite sophisticated, that not only are space-efficient but also
efficiently support a large subset of the desired queries.