What GraphRepresentations does Mathematica use?

Question

Mathematica can use multiple internal representations for Graphs. Normally, we don't need to care about this. But the specific representation used can influence the performance of some functions, and is relevant to understanding some bugs and coming up with useful workarounds.

The graph representation can be queried with

repr = GraphComputation`GraphRepresentation[g]

and set with

GraphComputation`ToGraphRepresentation[g, repr]

What are the possible values of repr and when can (or can't) they be used?

Answer 1

This is a community wiki answer. Feel free to extend or correct it.

---

The following values seem to be valid between Mathematica 10.0 – 11.3 (the latest version as of this writing).

g1 = Graph[{}, {}];

GraphComputation`GraphRepresentation[g1]
(* "NullGraph" *)

NullGraph is only valid for the graph with no vertices, and also the only representation usable for this graph.

g2 = Graph[{1 <-> 2}];

GraphComputation`GraphRepresentation[g2]
(* "Incidence" *)

Incidence seems to be valid for all graphs but the null graph.

g3 = AdjacencyGraph[{{0, 1}, {1, 0}}];

GraphComputation`GraphRepresentation[g3]
(* "Simple" *)

Simple seems to be valid for simple graphs only (i.e. no self-loops or multi-edges). It is not valid for the null graph.

g4 = AdjacencyGraph[{{1, 1}, {1, 0}}];

GraphComputation`GraphRepresentation[g4]
(* "Sparse" *)

Sparse seems to be valid for all graph but the null graph.

---

It does not seem to matter whether the graph is undirected, directed or mixed when looking at whether a certain representation can be used.