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.

i1 : R = QQ[a..z]; |

i2 : g6 = graphToString cycle R; #g6 o3 = 56 |

i4 : s6 = graph6ToSparse6 g6; #s6 o5 = 28 |

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.

i6 : g6 = graphToString completeGraph R; #g6 o7 = 56 |

i8 : s6 = graph6ToSparse6 g6; #s6 o9 = 327 |

- graph6ToSparse6 -- converts a Graph6 string to a Sparse6 string
- graphToString -- converts a graph to a string in the Graph6 format
- sparse6ToGraph6 -- converts a Sparse6 string to a Graph6 string
- stringToGraph -- converts a Sparse6 or Graph6 String to a Graph in the given polynomial ring