Using G & G with Graphs and Digraphs
Last update=20 Feb, 2001
Above is a typical graph window containing the line graph of the dodecahedron.
Graph Functions Available in G&G 3.0
Automorphism GroupThe automorphism group of a graph or digraph is calculated by partition refinement. See William Kocay, "On Writing Isomorphism Programs", in Computational and Constructive Design Theory, edited by W.D. Wallis, Kluwer Academic Publishers, 1996. See also B.D. McKay, "Practical graph isomorphism", Congressum Numerantium 30 (1981), 45-87, for a description of a partition refinement algorithm. Batch computation below gives further info on using G&G to calculate the automorphism group for files of graphs.
Long PathsAn implementation of an extended crossover algorithm that searches for a long path. The algorithm is described in W. Kocay and B. Li, "An algorithm for finding a long path in a graph", Utilitas Math. 45 (1994), 169-185. It is very fast and will often find a hamiltonian cycle or path if a graph has one. Also available for digraphs.
Hamilton CyclesA semi-intelligent exhaustive search for a hamilton cycle. The algorithm is described in W. Kocay, "An extension of the multi-path algorithm for hamilton cycles", Discrete Maths. 101, (1992), 171-188. The algorithm works well for trivalent graphs, whether hamiltonian or non-hamiltonian. Graphs of mininmum degree 4 or more can take a very long time. G&G can also save a file of all ham cycles in a graph.
Planar DualThe planarity test is based on a variant of the Hopcroft-Tarjan planarity algorithm. When a graph is found to be planar, its planar dual is automatically constructed. The flag tool then becomes available allowing faces of the graph to be selected. The nodes of the dual corresponding to the faces of the original graph can be indicated by "option-clicking". (The planarity algorithms are currently not implemented for digraphs.)
Planar LayoutOnce a graph has been found to be planar, this function becomes available. The planar layout algorithm is that of W. Kocay and C. Pantel, "An algorithm for finding a planar layout of a graph with a regular polygon as outer face", Utilitas Mathematica 48 (1995), 161-178. It is an extension of Read's algorithm, R.C. Read, "A new method for drawing a planar graph given the cyclic order of the edges at each vertex'', Congressus Numerantium 56 (1987), 31-44. A planar graph can also be pivoted so that any face is drawn as the outer face.
k-FactorsA k-factor of a graph is a k-regular subgraph. The algorithm used to find k-factors is described in W. Kocay and D. Stone, "Balanced network flows", Bulletin of the Institute of Combinatorics and its Applications 7 (1993), 17-32.
SymmetrizationGiven a graph X with n points, and a group G acting on n points, one can add edges to the graph X and symmetrize the graph to get the smallest graph containing these edges such that G acts as an automorphism group. For example, Cayley graphs and combinatorial designs with a prescribed group can be constructed in this way.
Draw SymmetricGiven a graph X with automorphsim group G, select a perm P in G to be used as a symmetry in the drawing of X. G&G will try to find a long cycle on which P acts as a symmetry, and then redraw the graph using this symmetry. If no symmetry is selected, G&G will select random perms in G and select the one with the largest number of points in cycles of the same length. It will then search for a drawing using this perm as symmetry. This works for graphs and digraphs. The algorithm is described in W. Kocay and H. Carr, "An algorithm for drawing a graph symmetrically", Bulletin of the Institute of Combinatorics and its Applications 27 (1999), 19-25.
Kempe ChainsIn a coloured graph, select two adjacent nodes of different colours, say R&B, and find the Kempe chain containing them. This is the connected subgraph using colours R&B. Then flip the Kempe chain to produce a new colouring.
Batch ComputationGiven a graph X, G&G will write out a file of all vertex-deleted or edge-deleted subgraphs. Input this file or other files of graphs, to Aut(X) to find the automorphism group of every graph in the file. The graph certificates can be written to another file, and sorted, with duplicates removed. This finds the automorphism types of large files of graphs.
Random GraphsRandom graphs can be constructed with specified edge-probability. These graphs are pseudo-random, such that each edge occurs with constant probability. The points are placed on a square grid. G&G will also construct random planar triangulations and their duals. These graphs are constructed using a randomized technique based on a reduction using vertices of degrees 3, 4, and 5. They are random only in the sense that the graph produced is not predetermined. The relative proportions of vertices of degrees 3, 4, 5 can be adjusted. G&G will also construct random subgraphs and random orientations of a given graph.
Also...Line Graphs, Neighbour Graphs, Antipodal Graphs, Distance-k Graphs, Bipartite Doubles, Complements, Strong Components, Converse, test for Strongly Regular Graphs, plus a variety of graph and digraph editing functions. Back to the Groups & Graphs home page.