sparse6

sparse6 (extension .s6) is a compact ASCII encoding for undirected graphs, created by Brendan McKay of the Australian National University as part of his nauty graph-automorphism toolkit. It is the sparse-graph companion to McKay's dense Graph6 and to the directed digraph6, sharing their design goal: represent a graph as a single line of printable characters (byte values 63-126) so graphs can be stored one-per-line in plain text files, emailed, and stream-processed without binary handling. An optional file-level header, the literal string ">>sparse6<<", may precede the data.

Where graph6 encodes the upper triangle of the adjacency matrix bit-by-bit (efficient only when edges are dense), sparse6 encodes an explicit edge list, making it far more space-efficient for large graphs with relatively few edges. Each sparse6 line begins with a colon (":"), which is how readers distinguish it from graph6. The colon is followed by N(n), the same variable-length vertex-count encoding graph6 uses (1, 4, or 8 bytes, supporting orders from 0 up to 68,719,476,735). The remaining six-bit groups encode a sequence of (b, x) pairs: a one-bit "increment" flag b that advances a running current-vertex pointer v, and a k-bit field x (k = ceil(log2 n)) giving the other endpoint. Decoding walks the pairs, emitting edge {x, v} whenever x <= v; a specific rule pads the final group with 0- and 1-bits to reach a multiple of six. Unlike graph6, sparse6 permits loops and multiple edges, though McKay notes nauty's own utilities have historically had limited support for those.

In the format-conversion landscape sparse6 is a niche but well-supported interchange format for combinatorial and mathematical graph collections rather than attributed or labelled network data: it carries only unlabelled structure, with no vertex/edge attributes, weights, coordinates, or metadata, so it contrasts sharply with rich formats like GraphML or GEXF. It is read and written by nauty/Traces, by NetworkX and igraph, and by dedicated libraries such as the R package rgraph6, and it appears throughout McKay's own graph databases. Its strengths are extreme compactness for sparse graphs, human-transmissible single-line text, and canonical use in enumeration research; its limitations are the attribute-free data model, undirected-only scope (directed graphs need digraph6), and an opaque bit-packed encoding that is not human-readable and requires a conforming codec to interpret.