G&G Algorithms Last update=3 Feb, 2015 This page provides references for some of the algorithms used in Groups & Graphs.
Graph IsomorphismThe 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), 4587, for a description of a partition refinement algorithm.
Hamilton CyclesHamilton cycles are found using an exhaustive search technique. The algorithm is described in W. Kocay, "An extension of the multipath algorithm for hamilton cycles", Discrete Maths. 101, (1992), 171188 (76K). The algorithm has been substantially improved by Andrew Chalaturnyk, A Fast Algorithm for Finding Hamilton Cycles.
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), 169185 (164K).
Planarity TestThe planarity test is based on a variant of the HopcroftTarjan planarity algorithm. It is described in W. Kocay, "The HopcroftTarjan Planarity Algorithm", unpublished (212K).
Planar Graph LayoutThe 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), 161178 (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), 3144.
Draw SymmetricThe drawsymmetric 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), 1925 (116K).
kFactorsA balanced flow algorithm is used to find kfactors of graphs, W. Kocay and D. Stone, "An Algorithm for Balanced Flows", J. of Combinatorial Mathematics and Combinatorial Computing 19 (1995), 331 (80K), and W. Kocay and D. Stone, "Balanced Network Flows", Bulletin of the Institute of Combinatorics and its Applications 7 (1993), 1732 (68K).
Torus MapsThe torus layout algorithm is described in W. Kocay, D. Neilson, and R. Szypowski, "Drawing Graphs on the Torus", Ars Combinatoria 59 (2001), 259277 (172K). A surveytype 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. 251171. It contains a classification of all torus 2cell 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 K_{5} subdivision is solved in A. Gagarin and W. Kocay, "Embedding Graphs Containing K_{5} Subdivisions", Ars Combinatoria 64 (2002), 3350 (160K). A lineartime algorithm for this special case is relatively easy to implememnt.
Projective ConfigurationsThe 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), 171191 (184K); and in W. Kocay and R. Szypowski, "The Application of Determining Sets to Projective Configurations", Ars Combinatoria 53 (1999), 123145 (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 GroupsA modification of the ScheierSims algorithm is used for generating permutation groups. It is described in W. Kocay, "A modification of the SchreierSims algorithm utilising the transitivity of the stabiliser subgroups", J. Combinatorial Mathematics and Combinatorial Computing 31 (1999), 193206 (136K).
Back to the Groups & Graphs home page.
