Classification of robust cycle bases and relations to fundamental cycle bases

  • Alexander Reich Brandenburg University of Technology, Germany
Keywords: Minimum cycle basis, robust cycle basis, quasi-robust cycle basis, fundamental cycle basis


The construction of a cycle in a graph can be realized by iteratively adding cycles of a cycle basis. The construction of each elementary cycle is only possible if this cycle basis is robust. In the last years, different classes of robust cycle bases have been established. We compare these classes and show that they are completely unrelated. More precisely, we draw a Venn diagram which displays the obvious containedness relations and show that each of its regions is not empty. In addition, we continue the comparison with fundamental cycle bases.