Articles and Algorithms

Last update=7 Sept, 2018

hrule

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. This article describes the general method of partition refinement, combined with automorphism groups, and includes techniques for programming graph isomorphism efficiently. See also B.D. McKay, "Practical graph isomorphism", Congressum Numerantium 30 (1981), 45-87, for a description of a partition refinement algorithm.

The automorphism group of a 3-regular graph can be found in polytime, as proved by Luks in 1980. A method of coding the algorithm to improve efficiency is presented in W. Kocay, "On Isomorphism Testing in 3-Regular Graphs", Journal of Comp. Math. and Comp. Computing 1 (1987), 131-140.

Hamilton Cycles

Hamilton cycles are found using a variation of the multi-path algorithm -- 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. The algorithm has been substantially improved by Andrew Chalaturnyk, A Fast Algorithm for Finding Hamilton Cycles, M.Sc. Thesis (2008), University of Manitoba.

Long Paths

Long paths are found by a variation of the extended crossover algorithm. 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.

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", (1993), unpublished.

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. 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. Together with the method of coordinate averaging, described in "Graphs, Algorithms, and Optimization" (2nd edition, 2016), by Kocay and Kreher, very nice drawings of 3-connected planar graphs are obtained.

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. It uses the cycles of an automorphism to construct a symmetric drawing of a graph.

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, and W. Kocay and D. Stone, "Balanced Network Flows", Bulletin of the Institute of Combinatorics and its Applications 7 (1993), 17-32.

Torus Maps

A rotation system of a graph embedded on an oriented surface consists of a cyclic list of the incident edges for each vertex. This is sufficient to determine the facial cycles of the embedding. Given a toroidal rotation system for a graph, 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. When this is combined with the method of coordinate averaging, described in "Graphs, Algorithms, and Optimization" (2nd edition, 2016), by Kocay and Kreher, very nice drawings of torus maps are obtained.

A survey-type paper on torus embeddings is A. Gagarin, W. Kocay, and D. Neilson, "Embeddings of Small Graphs on the Torus" (2001), 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.

See also the page of torus updates which corrects a few errors in the Cubo paper.

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 which cannot be converted to a K3,3 subdivision is solved in A. Gagarin and W. Kocay, "Embedding Graphs Containing K5 Subdivisions", Ars Combinatoria 64 (2002), 33-50. This was extended in A. Gagarin and W. Kocay, "Embedding Graphs Containing K5 Subdivisions on the Torus", J. Comb. Math. and Comb. Comp. 80 (2012), 207-223. A linear-time algorithm for this special case is relatively easy to implement.

Projective Maps

The algorithm used by G&G to determine whether a graph can be embedded in the projective plane is based on bridges. It is described in "Graphs, Algorithms, and Optimization" (2005), by Kocay and Kreher. It produces a signed rotation system, which is necessary for unorientable surfaces. The algorithm for finding a drawing on the projective plane is similar to the algorithm for the torus, and also uses coordinate averaging.

Graph Embedding Algorithms

Several published polytime algorithms for determining whether a graph can be embedded on the torus contain errors which cannot be corrected while maintaining polytime. This is described in W. Myrvold and W. Kocay, "Errors in Graph Embedding Algorithms" (2007), J. of Computer and System Sciences 77 (2011), 430-438.

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; and in W. Kocay and R. Szypowski, "The Application of Determining Sets to Projective Configurations", Ars Combinatoria 53 (1999), 123-145. 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.

(n3) Configurations

The Georges configuration is a (253) configuration. An integer coordinatization of it is constructed in W. Kocay, "A Note on the Georges Configuration and a Paper of Grünbaum", Bulletin of the ICA 58 (2010), 103-111.

An (n3) configuration is said to be a theorem if after removing any one incidence, and drawing the resulting configuration, the missing incidence is guaranteed. The Pappus and the Desargues configurations are both theorems. One of the (103) configurations is "almost a theorem". This is described in W. Kocay, "A 103 configuration that is almost a theorem", Bulletin of the ICA 68 (2013), 33-39.

A one-point extension of an (n3) configuration creates an ((n+1)3) configuration. The construction is described in W. Kocay, "One-point extensions in (n3) configurations", Ars Math. Contemp. 10 (2016), 291-322. The configurations which can be obtained by one-point extensions are characterised.

A central question in (n3) configurations is whether they can be drawn in the plane with straight lines. The (73) and (83) configurations cannot be drawn, but the three (93) configurations and nine of the ten (103) configurations can be drawn, as well as all of the (113) and (123) configurations. Those that can be drawn in the plane can all be drawn such that the points all have rational coordinates. When a configuration arises as a one-point extension, a rational coordinatization can usually be constructed as part of the extension. This is described in W. Kocay, "Coordinatizing (n3) configurations", Ars Math. Contemp. 15 (2018), 127-145.

The Graph Reconstruction Problem

A theorem relating the subgraphs of a graph is useful for counting subgraphs in the graph reconstruction problem, W. Kocay, "Some New Methods in Reconstruction Theory", 1981, Ninth Australian Combinatorial Conference, Brisbane Australia, in Combinatorics IX, Lecture Notes in Mathematics #952, Springer-Verlag 1982, pp 89-114.

Let G and H be graphs with vertices {u1, u2, ..., un} such that G - ui is isomorphic to H - ui, for i = 1, 2, ..., n. The mappings pi from G - ui to H - ui can sometimes be used to prove that G and H are isomorphic. This is described in P. Ille and W. Kocay, "Graph Reconstruction by Permutations", Ars Combinatoria 86 (2008) 321-344.

Let G and H be two graphs on n+2 vertices, {u1, u2, ..., un, x, y}, where n ≥ 9, such that G-ui and H-ui are isomorphic, for i = 1, 2, ..., n. Then the number of edges of G and H differ by at most one. W. Kocay, "On Reconstructing Graphs from n - 2 Cards", J. Comb. Math. and Comb. Comp. 80 (2012) 5-10.

A construction using the automorphism groups of Paley graphs (quadratic residue graphs) is described in W. Kocay and D. Kreher, "On Reconstructing Graphs and their Complements", SIAM Journal of Discrete Mathematics 28 (2014), 1026-1034. A pair G, H of graphs on 2n vertices is constructed such that they have n cards in common (vertex-deleted subgraphs). G and H have the same degree sequences, they are connected, and their complements are connected.

Given graphs G1 and G2, the multiset union of their decks is
D[G1, G2] = D[G1] ∪ D[G2]. If G1 and G2 are trees with at least five vertices, then they are uniquely determined by D[G1, G2]. If G1 and G2 are disconnected graphs with at least five vertices, then they are uniquely determined by D[G1, G2] iff the graph reconstruction conjecture is true. The reconstruction of k graphs G1, G2, ..., Gk from their multi-deck D[G1, G2, ..., Gk] is explored in W. Kocay, "Some Constructions for k-Reconstruction", Ars Combinatoria 6 (1978) 3-17.

Hypergraphs

A simple 3-hypergraph on a vertex set V consists of a subset of the set of triples of vertices from V. Given two simple 3-hypergraphs G and H, with the same degree sequence, it is always possible to transform G into H by a sequence of exchanges, such that all intermediate 3-hypergraphs are also simple. This is shown in W. Kocay and Pak-Ching Li, "On Degree Sequences of Hypergraphs", Ars Combinatoria 82 (2006), 145-157.

A partial Steiner triple system is a simple 3-hypergraph G with the property that any pair {u,v} of vertices occurs in at most one triple of G. Conditions similar to the Erdös-Gallai conditions on the degree sequence of a simple graph apply to partial Steiner triple systems. They are described in M. Keränen, W. Kocay, D. Kreher, P.K. Li, "Degree Sequence Conditions for Partial Steiner Triple Systems", Bulletin of the ICA 57 (2009), 71-73.

There are a number of non-reconstructible 3-hypergraphs. Those on at most 8 vertices and 11 triples are catalogued in W. Kocay, "A Note on Non-reconstructible 3-Hypergraphs", Graphs and Combinatorics 32 (2016) 1945-1963. In particular there is a triple {G,H,K} of 3-hypergraphs on 6 vertices and 10 triples which are pairwise hypomorphic. A 3-hypergraph has induced 3-sub-hypergraphs as well as induced subgraphs. Some counting relations amongst them are also proved.

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.

Graph Factorizations

A variation of a 1-factorization of a graph is a butterfly factorization. It has a special 1-factor, each of whose edges appears in two 1-factors. Several papers with Ralph Stanton investigate these.
W. Kocay and R.G. Stanton, "On Butterfly Factorizations", Bulletin of the ICA 55 (2009), 57-65.
W. Kocay and R.G. Stanton, "Butterfly Factorizations of K8", Utilitas Mathematica 79 (2009), 221-225.
W. Kocay and R.G. Stanton, "On Metamorphosis of Butterfly Factorizations", Bulletin of the ICA 57 (2009), 29-34.

Finite Projective Planes

A quadrangle in a projective plane consists of four points {A, B, C, D}, such that no three are collinear. They determine six lines AB, AC, AD, BC, BD, CD. There are three points of intersection E = AB ∩ CD, F = AC ∩ BD, G = AD ∩ BC. If E, F, G are collinear, then {A, B, C, D} is a Fano quad. If they are non-collinear, then {A, B, C, D} is a non-Fano quad. The types of quadrangles can be used to characterize a projective plane.

Quads are used to characterize some of the small projective planes in W. Kocay and R.G. Stanton, "Fano Quads in Projective Planes", Ars Combinatoria 58 (2001), 217-223. An interesting configuration in the Hughes plane is also discovered.

A sum of squares theorem using non-Fano quads is used to characterize the plane of order 7 in W. Kocay, "Non-Fano Quads in Finite Pro jective Planes ", Ars Combinatoria 83 (2007), 65-92.

Four-Colour Theorem

A fast heuristic for 4-colouring a planar graph is described in H. Carr and W. Kocay, "A Heuristic for 4-Colouring a Planar Graph", J. Comb. Math. Comb. Comp. 46 (2003), 97-112. A proof that it always works would be an alternative proof of the 4-Colour Theorem.

hrule

G&G     Back to the Groups & Graphs home page.