Graphs

Changes:

• The function Bicomponents now returns the bicomponents as a sequence of subsets of the graph's vertex set, instead of a sequence of subgraphs as previously.

• The functions DFSTree($v$) and BFSTree($v$) may now apply to disconnected graphs too: the tree returned is simply the search tree rooted at vertex $v$.

• The functions IsDistanceTransitive, IsTransitive, IsPrimitive, IsSymmetric,
  IsEdgeTransitive, EdgeGroup, OrbitsPartition, IsIsomorphic, and CanonicalGraph no longer accept user parameters. Whenever parameters are needed to drive the computation of the graph's automorphism group, users may set the appropriate parameters when calling AutomorphismGroup.

New Features:

• It is now possible to construct graphs with a sparse representation: That is, the graph is internally represented by means of its adjacency list.

  If no specification is given at the time of constructing the graph, or if the called Magma function does not allow for such a specification to be given, the graph is always represented by means of its adjacency matrix (the dense representation).

  Not all existing Magma functions have been -yet- rewritten with the new sparse representation in mind. Should internal specifications of a Magma function require a different graph representation than the current one, then the required conversion takes place automatically, without user intervention.

  The primary purpose of introducing the sparse representation is the implementation of a planarity tester.

• A linear planarity tester and a linear obstruction isolator due to Boyer and Myrvold has been implemented. One tests if a graph $G$ is planar by calling IsPlanar($G$). This functions also returns the obstruction as a subgraph of $G$ should $G$ be non-planar.

  If $G$ is planar, additional functionalities allow the computation of $G$'s faces (Faces($G$)), and of $G$'s embedding (Embedding($G$)).

  The planarity tester may be applied to any undirected graph, connected or not.

• It is now possible to determine the strongly connected components of a digraph
  (StronglyConnectedComponents).

Bug Fixes:

• The Magma interface for the nauty program that computes the automorphism group of a graph AutomorphismGroup has been improved so that the efficiency of the Magma call to nauty is as close as possible to the efficiency of a call to nauty outside of Magma's interface.

• In this same interface, a memory allocation problem has been fixed. Because of this allocation problem, AutomorphismGroup could previously return wrong answers.

• The function StronglyRegularGraphsDatabase now reads the catalogue of strongly regular graphs correctly.