The program nauty uses two string-based formats for storing graphs: Graph6 and Sparse6 format. Each format has benefits and drawbacks.
In particular, the length of a Graph6 string representation of a graph depends only on the number of vertices. However, this also means that graphs with few edges take as much space as graphs with many edges. On the other hand, Sparse6 is a variable length format which can use dramatically less space for sparse graphs but can have a much larger storage size for dense graphs.
Consider the 26-cycle, a rather sparse graph. Notice how Sparse6 format takes half the space of the Graph6 format.
|
|
|
However, the complete graph, which is as dense as possible, on 26 vertices is the opposite: the Sparse6 format takes nearly six times the space of the Graph6 format.
|
|
|