Cycle basis

A spanning subgraph of a given graph G has the same set of vertices as G itself but, possibly, fewer edges.

A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has even degree (its number of incident edges).

The cycle space of a graph is the collection of its Eulerian subgraphs.

It forms a vector space over the two-element finite field.

The vector addition operation is the symmetric difference of two or more subgraphs, which forms another subgraph consisting of the edges that appear an odd number of times in the arguments to the symmetric difference operation.

It consists of a set of cycles that can be combined, using symmetric differences, to form every Eulerian subgraph, and that is minimal with this property.

This number is called the circuit rank of the graph, and it equals

Each of them is linearly independent from the remaining cycles, because it includes an edge

if and only if it has the independence property and has the correct number of cycles to be a basis of

Based on this property, the class of graphs (and multigraphs) for which every cycle basis is weakly fundamental can be characterized by five forbidden minors: the graph of the square pyramid, the multigraph formed by doubling all edges of a four-vertex cycle, two multigraphs formed by doubling two edges of a tetrahedron, and the multigraph formed by tripling the edges of a triangle.

For graphs properly embedded onto other surfaces so that all faces of the embedding are topological disks, it is not in general true that there exists a cycle basis using only face cycles.

The face cycles of these embeddings generate a proper subset of all Eulerian subgraphs.

characterizes the Eulerian subgraphs that cannot be represented as the boundary of a set of faces.

Mac Lane's planarity criterion uses this idea to characterize the planar graphs in terms of the cycle bases: a finite undirected graph is planar if and only if it has a sparse cycle basis or 2-basis,[3] a basis in which each edge of the graph participates in at most two basis cycles.

In a planar graph, the cycle basis formed by the set of bounded faces is necessarily sparse, and conversely, a sparse cycle basis of any graph necessarily forms the set of bounded faces of a planar embedding of its graph.

An important special case is the ring of integers, for which the homology group

Less abstractly, this group can be constructed by assigning an arbitrary orientation to the edges of the given graph; then the elements of

His algorithm uses this generate-and-test approach, but restricts the generated cycles to a small set of

There are at most n different shortest path trees (one for each starting vertex) and each has fewer than m fundamental cycles, giving the bound on the total number of Horton cycles.

[13] Using Dijkstra's algorithm to find each shortest path tree and then using Gaussian elimination to perform the testing steps of the greedy basis algorithm leads to a polynomial time algorithm for the minimum weight cycle basis.

Subsequent researchers have developed improved algorithms for this problem,[14][15][16][17] reducing the worst-case time complexity for finding a minimum weight cycle basis in a graph with

[18] Finding the fundamental basis with the minimum possible weight is closely related to the problem of finding a spanning tree that minimizes the average of the pairwise distances; both are NP-hard.

[19] Finding a minimum weight weakly fundamental basis is also NP-hard,[7] and approximating it is MAXSNP-hard.

[21] Based on this duality, an implicit representation of the minimum weight cycle basis in a planar graph can be constructed in time

[23] In the theory of structural rigidity and kinematics, cycle bases are used to guide the process of setting up a system of non-redundant equations that can be solved to predict the rigidity or motion of a structure.

In this application, minimum or near-minimum weight cycle bases lead to simpler systems of equations.

[24] In distributed computing, cycle bases have been used to analyze the number of steps needed for an algorithm to stabilize.

[25] In bioinformatics, cycle bases have been used to determine haplotype information from genome sequence data.

[26] Cycle bases have also been used to analyze the tertiary structure of RNA.

[27] The minimum weight cycle basis of a nearest neighbor graph of points sampled from a three-dimensional surface can be used to obtain a reconstruction of the surface.