Sparse Graphs

As mentioned in the Introduction Introduction of this chapter it is now possible to construct graphs having a sparse representation. That is, graphs which are represented by means of an adjacency list. This has obvious advantage for graphs with a low edge density, in that it allows to construct much larger graphs than if they were to be represented by means of an adjacency matrix (the dense representation).

Another advantage of the sparse representation is for graph algorithms which are linear in the number of edges. This is the case of the planarity tester in particular.

Only a handful of existing Magma functions have been specifically rewritten for the sparse representation. Should a function designed for a matrix representation be applied to a graph with a sparse representation, then the graph is automatically converted without any user intervention.

Without being exhaustive, we will list here the functions for which the graph's sparse representation remains unchanged; in case of doubt some tools are provided below to help determine what the representation of a graph is. Note that almost all graph representation conversions involve going from a sparse representation to a dense representation. Only the planarity functionalities require the reverse conversion.

We now give an overview of the functions that do not need to convert the graph's sparse representation:

• Nearly all construction functions (Construction of Graphs and Digraphs)
• All functions in The Vertex--Set and Edge--Set of a Graph, Labelled Graphs, Subgraphs, Quotient Graphs, and Super-graphs, Incremental Construction of Graphs
• Some functions in Constructing Complements, Line Graphs; Contraction, Switching
• All functions in Converting between Graphs and Digraphs
• The basic predicates in Elementary Graph Predicates
• Almost all functions in Adjacency, Degree and Distance
• All functions in Connectedness in a Graph and all but the last in Connectedness, Paths and Circuits in a Digraph
• All functions in Spanning Trees of a Graph or Digraph and, of course, in Planar Graphs

HasSparseRep(G) : Grph -> BoolElt

HasDenseRep(G) : Grph -> BoolElt

HasSparseRepOnly(G) : Grph -> BoolElt

HasDenseRepOnly(G) : Grph -> BoolElt

HasDenseAndSparseRep(G) : Grph -> BoolElt

This set of functions determine the nature of a graph's representation. Note that when converting a graph's representation into the alternative one the original representation is not deleted.

Example Graph_SparseReps (H97E6)

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
> HasDenseRepOnly(G);
true
> A := AutomorphismGroup(G);
> HasDenseRepOnly(G);
true

The same example using a sparse graph representation:

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> A := AutomorphismGroup(G);
> HasDenseAndSparseRep(G);
true

Next the case when the graph's sparse representation remains unchanged:

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> IsPlanar(G);
true
> HasSparseRepOnly(G);
true

Finally the same example using a dense graph representation:

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
> HasDenseRepOnly(G);
true
> IsPlanar(G);
true
> HasDenseAndSparseRep(G);
true