Last update=3 Feb, 2015
Graph Isomorphism
The automorphism group of a graph or digraph is calculated by partition refinement. See W. Kocay, "On Writing Isomorphism Programs", in Computational and Constructive Design Theory, edited by W.D. Wallis, Kluwer Academic Publishers, 1996. (The link is a scan of the original paper). See also B.D. McKay, "Practical graph isomorphism", Congressum Numerantium 30 (1981), 45-87, for a description of a partition refinement algorithm.
Hamilton Cycles
Hamilton cycles are found using an exhaustive search technique. The algorithm is described in W. Kocay, "An extension of the multi-path algorithm for hamilton cycles", Discrete Maths. 101, (1992), 171-188 (76K). The algorithm has been substantially improved by Andrew Chalaturnyk, A Fast Algorithm for Finding Hamilton Cycles.
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 (164K).
Planarity Test
The planarity test is based on a variant of the Hopcroft-Tarjan planarity algorithm. It is described in W. Kocay, "The Hopcroft-Tarjan Planarity Algorithm", unpublished (212K).
Planar Graph Layout
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 (180K). 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.
Draw Symmetric
The draw-symmetric 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 (116K).
k-Factors
A balanced flow algorithm is used to find k-factors of graphs, W. Kocay and D. Stone, "An Algorithm for Balanced Flows", J. of Combinatorial Mathematics and Combinatorial Computing 19 (1995), 3-31 (80K), and W. Kocay and D. Stone, "Balanced Network Flows", Bulletin of the Institute of Combinatorics and its Applications 7 (1993), 17-32 (68K).
Torus Maps
The torus layout algorithm is described in W. Kocay, D. Neilson, and R. Szypowski, "Drawing Graphs on the Torus", Ars Combinatoria 59 (2001), 259-277 (172K). A survey-type paper on torus embeddings is A. Gagarin, W. Kocay, and D. Neilson, "Embeddings of Small Graphs on the Torus" (2001), (260K) CUBO 5(2003), pp. 251-171. It contains a classification of all torus 2-cell embeddings of all connected vertex transitive graphs up to 12 vertices. It also contains nice pictures of many of the embeddings.G&G does not currently have an algorithm implemented for determining whether an arbitrary graph can be embedded on the torus. The special case of embedding a graph containing a K5 subdivision is solved in A. Gagarin and W. Kocay, "Embedding Graphs Containing K5 Subdivisions", Ars Combinatoria 64 (2002), 33-50 (160K). A linear-time algorithm for this special case is relatively easy to implememnt.
Projective Configurations
The algorithms used to animate projective drawings are described in W. Kocay and D. Tiessen, "Some algorithms for the computer display of geometric constructions in the real projective plane", J. of Comb. Maths. and Comb. Computing 19 (1995), 171-191 (184K); and in W. Kocay and R. Szypowski, "The Application of Determining Sets to Projective Configurations", Ars Combinatoria 53 (1999), 123-145 (144K). In this paper the existence of determining sets in (n,3)-configurations is used to prove results about the coordinatizability of some (n,3)-configurations.
Permutation Groups
A modification of the Scheier-Sims algorithm is used for generating permutation groups. It is described in W. Kocay, "A modification of the Schreier-Sims algorithm utilising the transitivity of the stabiliser subgroups", J. Combinatorial Mathematics and Combinatorial Computing 31 (1999), 193-206 (136K).
