  In order to manage massive graphs in practice, it is often necessary to
resort to graph compression, which aims at reducing the memory used when
storing and processing the graph. Efficient compression methods have been
proposed in the literature, especially for web graphs. In most cases, they are
combined with a vertex reordering pre-processing step which significantly
improves the compression rate. However, these techniques are not as efficient
when considering other kinds of graphs. In this paper, we focus on the class of
bipartite graphs and adapt the vertex reordering phase to their specific
structure by proposing a dual reordering scheme. By reordering each group of
vertices in the purpose of minimizing a specific score, we show that we can
reach better compression rates. We also suggest that this approach can be
further refined to make the node orderings more adapted to the compression
phase that follows the ordering phase.
