Short Cycles in Graphs

Cycles are one of the most basic and most important features of graphs. It is well known that the set of cycles, interpreted as edge sets, forms a vector space over GF(2). Short cycles are of particular practical interest for example in the analysis of large networks and in the context of chemical structure search. Thus we focus our work on minimum length cycle bases (in the chemical literature often called SSSRs) and the set of relevant cycles, which is defined as the union of all minimal cycle bases. We investigate the structure of minimum length cycles bases for various classes of graphs, including outerplanar graphs, Halin graphs, and product graphs. Methods for efficiently computing the relevant cycles are extended to directed graphs and to Hartvigsen's U-space, which consists of the cycles and all paths with endpoints in given vertex subset. The latter construction is useful for the investigation e.g. of metabolic networks.

(from Dietmar Kuck (1998) Top Curr Chem 196: 167-220)