Sparse Graphs

As mentioned in the 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 an 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 flow-based algorithms, the planarity tester and the triconnectivity tester. Further, the sparse representation is required when creating networks (see Chapter NETWORKS) which may have multiple edges.

A significant number, but not all, of the 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 needs no internal conversion; 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 vertex/edge connectivity, planarity and triconnectivity functionalities (might) 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 and Quotient 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 second 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 conversion of the graph's representation into the alternative one occurs the original representation is not deleted.

Example Graph_SparseReps (H102E6)

> 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