Last update=20 Feb, 2001
Above is a typical graph window containing the line graph of the dodecahedron.
A subgraph with 5 edges is emphasized in bold.
- The arrow tool is for selecting and moving nodes
- The pencil is for editing the graph, edges are added or deleted as the pencil clicks from node to node
- The fat pencil is for editing the bold subgraph. It adds or deletes thick edges as the mouse is clicked
- The sputnik creates a new node attached to all currently selected nodes, at the point where the mouse is clicked
- The bullet creates or deletes nodes, where the mouse is clicked
- The hand moves the graph within the window
- The flag selects and highlights a face of a graph known to be planar
- The thermometer selects vertices by colour, and paints nodes a selected colour
- The certificate is a character string that identifies a graph up to isomorphism, that is, isomorphic graphs will have equal certificates.
A digraph window is similar to a graph window. Digraphs may also have bold subgraphs. Edges oriented in both directions are shown with no arrow. This particular digraph is a Cayley graph of the alternating group A4. Some of the editing functions are slightly different for digraphs. The flag tool is not yet supported for digraphs.
Graph Functions Available in G&G 3.0
Automorphism Group
The 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 Paths
An 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 Cycles
A 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 Dual
The 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 Layout
Once 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-Factors
A 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.Symmetrization
Given 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 Symmetric
Given 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 Chains
In 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 Computation
Given 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 Graphs
Random 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.